PROBLEM LINK:Practice Setter: Данило Мочернюк DIFFICULTY:Hard. PREREQUISITES:Least Common Ancestor using Euler tour or Binary lifting, Centroid decomposition. Partial Sums. PROBLEM:Given a tree with $N$ nodes and an array $K$ of length $N$, for each node $u$, calculate the maximum value $D[i]$ such that the number of nodes at distance greater than $D[i]$ is at least $K[i]$. QUICK EXPLANATION
EXPLANATIONFirst of all, subtask 1 is easy to pass. We can just, for every node, run a DFS with that node as root and count the number of nodes at each value of distance, which we can use to answer for the current node, solving the problem in $O(N^2)$ time. We need a faster solution. To proceed further, knowledge of Centroid decomposition is a must. Here's an excellent resource. Let us decompose the tree into the centroid tree. Centroid of a tree refers to any node, the removal of which divide the remains of the tree into a forest, maximum tree size being no more than half the number of nodes. This guarantees depth at most $logN$. An important property of centroid tree is that the LCA of any pair of nodes $u$ and $v$ remain same. This allows us to split path from $u$ to $v$ into path from $u$ to LCA(u,v) to node $v$. The distance between each pair of nodes can be calculated using preprocessing, by common LCA finding methods like using RMQ over Euler tour (preferred) or using binary lifting. Suppose we decomposed the tree into centroid tree. For each node $x$ in centroid tree, we can run a DFS in a subtree, calculating the number of nodes at distance $\geq d$ for all $0 \leq d \leq s$ where $s$ is the size of the subtree of $u$. Also, we need to calculate the number of nodes in the subtree of node $u$ at each distance value from the parent of $u$ in centroid tree. We shall see why. Explaining in one line, it is because subtree of an ancestor of a node also includes the subtree of the current node. So, to exclude it, we need to calculate the number of nodes at distance di from the parent of the node too, so as to avoid doublecounting of nodes. For example, Consider tree as example with seven nodes where there's an edge between $i$ and $i+1$ nodes for every $0 \leq i < N1$. The centroid tree looks like as shown in the image. Let us count the number of nodes at distance $\geq 3$ from node 4. Considering the only subtree of node 4, there is no node at distance $\geq 3$ from node 4. Moving to its ancestor node $5$ now. Distance from node $4$ to $5$ is 1, so, we need to count only nodes at distance $\geq 31 = 2$ from node 5. There is no such node in the subtree of node $5$ at distance $\geq 2$ from node 5. Climb over to its ancestor node $3$. The distance of node $3$ from node $4$ is 1, so we need to count the number of nodes in the subtree of node $3$ at distance $\geq 31 = 2$. There are four such nodes, namely node 0,1,5,6. But node $5$ and node $6$ are not to be considered, as they were part of the subtree of node $5$ which is already considered. So, we need to exclude these two nodes. This requires to calculate the number of nodes in the subtree of a node, at each distance $\geq d$ from the parent of the node in centroid tree. So, for subtree of node 5, there are two nodes (5 and 6) which are at distance $\geq 3dist(3,4) = 2$ from node $3$. So, excluding it from four nodes we found, we get two nodes at distance $\geq 3$ from node 4. We can easily verify its correct. Partial sums are needed here because DFS gives us the number of nodes at distance $x$. To translate it into Number of nodes at distance $\geq x$, we take suffix sum array. Now that we know how to count the number of vertices at distance $di$ from any node, we can run a binary search on the maximum value of $di$ for each node to obtain the answer. Time Complexity AnalysisThe time complexity for preprocessing takes $O(N*log(N))$ time for precomputing RMQ, Euler tour takes $O(N)$ time and centroid decomposition also takes $O(N)$ time. Running DFS over each centroid subtree takes $O(N*log(N))$ time as each node is present in at most $logN$ subtrees. For each node, the binary search takes $O(logN)$ and within each binary search, we have to move over all ancestors of a node, which also takes $O(logN)$ time. If LCA takes $O(1)$ time using RMQ, we can calculate maximum distance in $O(N*log^2(N))$ time. So, overall complexity comes out to be $O(N*log^2(N))$. Memory complexity is $O(N*log(N))$. For practice, the problems mentioned in blog would do. AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 14 Feb, 00:21

I am unable to see the codes of author, setter, and editorialist. answered 20 Feb, 13:54

@taran_1407 I am unable to see the codes of author, setter, and editorialist answered 21 Feb, 13:05
Pinged admin. Meanwhile, my solution https://ideone.com/hwkgw1
(21 Feb, 13:50)
