dododo89's blog

By dododo89, history, 4 years ago, In English

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?

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
4 years ago, # |
Rev. 5   Vote: I like it +17 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can u explain what are you storing at each ancestor?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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 years ago, # |
Rev. 5   Vote: I like it +4 Vote: I do not like it

NVM wrong.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For every node $$$u$$$, how do you consider path to a node $$$v$$$ such that $$$lca(u, v) \notin [u, v]$$$?