PROBLEM LINK:Author: Konstantin Sokol DIFFICULTY:HARD PREREQUISITES:heavy light decomposition, segment tree PROBLEM:There are N persons in Mike's school. No person in the school has a name(except Mike), but all of them have a unique ID number for the range[1..N]. Mike's ID equals to 1. Also, each person(except Mike) has his/her personal idol, who is another person from the school. Finally, each person has a number A[X]. Let's define functions F and G for a person: If X = 1(which means that person X is Mike), then F _{ X } = A _{ X } and G _{ X } = 1; It's guaranteed, that it's possible to calculate functions F and G for every person in the school. You are to write a program, that can efficiently process queries of the following types: QUICK EXPLANATIONThe line "It's guaranteed, that it's possible to calculate functions F and G for every person in the school." and constraint in the problem that P _{ i } < i ensures that graph is a rooted tree at the root 1. What does F[X] correspond to ? What does G_{ X } correspond to ? So now we can do heavy light decomposition of the tree and can answer the queries using a simple segment tree over the heavy edges. EXPLANATIONThe line "It's guaranteed, that it's possible to calculate functions F and G for every person in the school." and constraint in the problem that P _{ i } < i, ensures that graph is a rooted tree at the root 1. Each node corresponds to a person and each edge of the graph denotes the personal idol relationship between two persons. Formally, if person X has personal idol Y, then there would be an edge from Y to X. Note that the graph is tree with N nodes. Also note that root node has no personal idol. Interpretation of F_{ X } Let us understand definition of F[X].
Note that F[1] will be same as A[1]. What about F[X] for other than 1? Note the following properties of function F.
By using the previous properties, we can now say that F _{ X } = max(A _{ y } + distance between X and y) where y is a vertex on the path from root to X. Note that in a tree, distance between two nodes is equal to difference in depths of those nodes. So distance be X and y will be depth[X]  depth[y]. So F _{ X } = max(A _{ y } + depth[X]  depth[y]) where y is a vertex on the path from root to X. As for a fixed X, depth[X] is fixed, so we can take depth[X] out of the expression. So F _{ X } = depth[X] + max(A[y]  depth[y]) where y is a vertex on the path from root to X. Interpretation of G _{ X } Claim: Proof Ideas
Intiuitively, it means that if value of A[X]  depth[X] is equal to maximum value of A[y]  depth[y], then we will increase the count by 1.
Intiuitively, it means that we have found new value of max(A[y]  depth[y]), so we reset the count of max(A[y]  depth[y]) to 1.
Intiuitively, it means that if the current value of A[y]  depth[y] is less than max(A[y]  depth[y]), then it won't affect the max(A[y]  depth[y]) and it will also not effect the count of maximum value of A[y]  depth[y]. So count will remain constant. Using these observations you can get an intuition that these three operations correspond to updating the count of the number corresponding to the maximum of A[y]  depth[y]. How to deal with given queries Our node structure of the segment tree will contain two values max_val : the max value of A[v]  v and cnt: the count of the maximum value.
As the most important step in answering the queries in segment tree is how we are going to merge answer of the two nodes of the segment tree.
Heavy Light Decomposition of a tree (HLDOT) (This part of the explanation is taken from editorial of problem QUERY) If you can solve the problem for a chain using a segment tree, then there is a very good chance that you can solve the problem for a tree using HLDOT. Indeed, if you make segment trees over the heavy edges, then the answer for your path XY can be broken up into two paths from X to LCA(X, Y) and from Y to LCA(X, Y). Then, using that you make only logN shifts from one heavychain to another, you are actually making only log(N) segmenttree queries. In our case, either X or Y is 1. So lca is always root node. So we dont need to compute LCA explicitly. The heavylight decomposition is used to break up a Tree into s set of disjoint paths, with certain useful properties. First, root the tree. Then, for each vertex x, we find the child of x having the largest subtree. Lets call that vertex y. Then the edge xy is a heavy edge, and all other xchild_vertex edges are light edges. The most important property of this is, from any vertex x, the path from x to the root goes through at most logN different lightedges. This is because, on this path, whenever you take a light edge, you are atleast doubling the size of the subtree rooted at the new vertex. Hence you cannot perform this "doubling" effect more than logN times. Stack overflow Issue Complexity AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 23 Jun '14, 00:48
