### dododo89's blog

By dododo89, history, 4 weeks ago, ,

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 weeks ago, # | ← 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 weeks ago, # ^ |   0 can u explain what are you storing at each ancestor?
•  » » » 4 weeks ago, # ^ |   +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 weeks ago, # | ← Rev. 5 →   +4 NVM wrong.
•  » » 4 weeks ago, # ^ |   0 For every node $u$, how do you consider path to a node $v$ such that $lca(u, v) \notin [u, v]$?
•  » » » 4 weeks ago, # ^ |   0 Yeah, I wasn't. Thanks.