dododo89's blog

By dododo89, history, 4 weeks 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 weeks 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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can u explain what are you storing at each ancestor?

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

NVM wrong.

  • »
    »
    4 weeks 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]$$$?