### dododo89's blog

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