Блог пользователя dododo89

Nearest vertex in a tree with a smaller value
Автор dododo89, история, 4 года назад, По-английски

You are given a tree of $$$N<=10^6$$$ vertices. Each vertex of the tree contains a number $$$a[i]<=10^9$$$.You are given $$$M<=10^6$$$ queries: "Find the distance to nearest vertex to the vertex $$$V$$$, with the value less than $$$X<=10^9$$$?"

How this problem can be solved?

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

»
4 года назад, # |
← Rev. 5   Проголосовать: нравится +17 Проголосовать: не нравится

This can be solved with Centroid Decomposition in $$$O(n\log^{2} n)$$$. First build the centroid tree, and then for each query node $$$v$$$ look at all the ancestors of $$$v$$$ in the centroid tree and do a binary search in the precomputed vector for each ancestor. I think the constant is small here, so it should pass even with $$$10^6$$$ queries.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    can u explain what are you storing at each ancestor?

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Each centroid stores the distance for every node in its subtree (in the centroid tree). We can sort this list by value of the node and precompute prefix minimums, and then while answering the queries we just binary search to find the largest index whose corresponding node value is atmost $$$X$$$.

      → Ответить
»
4 года назад, # |
← Rev. 5   Проголосовать: нравится +4 Проголосовать: не нравится

NVM wrong.

→ Ответить