The idea of HLD , of breaking the tree into chains depending on the “special child” chosen can be extended to other problems as well. As an example, i shall explain the solution of the problem :
(you can read about HLD here http://blog.anudeep2011.com/heavy-light-decomposition/ )
http://codeforces.com/problemset/problem/526/G
Solution start :
Brief Explanation (Read detailed explanation for various proofs)
Step 1 : Hang the given tree at the center of the tree
Step 2 : Find the contribution of each leaf using HLD type idea.
Step 3 : Maintain a vector (sorted in decreasing order) of (contribution,node) pair node is the index of the leaf nodes.
Step 4 : Let leafcover[i] represent the leaf which covers node i in it’s contribution. Initially, leafcover[i] = 0. Come bottom-up from each leaf marking the nodes which are covered by this leaf, till leafcover[i] != 0 (because that node would have already be marked by some other leaf) .
Step 5 : Maintain a Prefix Sum over the contribution array.
Step 6 : For each query (x,y) :
if 2*y >= No of leaves
answer is sum of weights of all the edges because spiders can cover the whole tree
else if 2*y >= leafcover[x] //area covered by first 2*y greedily chosen leaves includes x
answer is prefix sum of first 2*y nodes in sorted vector
else //we need to remove some leaf and add x to the area.
We do a binary search for the first node lying on the path from x to root which is covered
by the first 2*y nodes (i.e. has leafcover <= 2*y ). Let this node be z .
Answer = PrefixSum[2*y] + LenghOfPathBetween(x-z) + LongestPathInSubtreeOf[x] -
min(contribution[2*y],LongestPathInSubtreeOf[z])
Detailed Explanation
Step 1 : Hang the given tree at the center of the tree
Claim : Let a,b be the end points (leaves) of the diameter of the given tree and let x be any arbitrary node of the tree. The farthest point from x in the given tree would definitely be one of a,b.
Proof : http://www.quora.com/How-does-following-algorithm-for-finding-longest-path-in-tree-work#
Claim : Let c be the center of the given tree and let x be any arbitrary node of the tree. The longest path in the tree passing the through x will definitely pass through the center c.
Proof : Imagine the given tree as a straight chain (the diameter) and all the remaining branches branching down from the leftchain or right chain or the center. (See example below)
a---(leftchain)--c--(rightchain)---b
|
|
(centralchain)
|
|
We just proved above that for any node x, the points farthest to x will either be a or b. Now x can lie either in leftchain/rightchain or the central chain. It is clear that
If x lies in leftchain, farthest point would be b
If x lies in rightchain, farthest point would be a
If x lies in central chain, farthest point would be a or be depending on max(dist(c,a),dist(c,b)).
In all 3 cases, the longest path passing through x would definitely pass through the center. (The above proofs for unweighted graph would also hold for a weighted graph because the center would be adjusted according to the distribution of the weights along the edges.)
Hence,having the above results, it is easy to see that for any x , if y==1, then we shall just cover the longest path containing x, which would definitely pass through the center. Hence for all y>=1 and any arbitrary x, center would always be in the final set of vertices which are covered by the spider web. Hence we root the tree by its center.
Step 2 : Find the contribution of each leaf using HLD type idea.
This is the important step we want to focus on. First i will give a sample code for what actually is happening.
Let dp[node] = represent the longest path coming from subtree of node till node.
dfs(node,currlen)
if(node is a leaf)
contribution.push_back(make_pair(currlen,node));
return
flag=0;
for all children w of node
if(dp[w] + edgeLength(node-w) < dp[node] OR flag==1) //not a special child
dfs(w, 0 + edgeLength(node-w))
else //special child, and it can be unique.
dfs(w, currlen + edgeLength(node-w))
flag = 1
The working of this code is left as an exercise to the reader. After the end, we would have found the contribution of each leaf of the tree.
Rest of the steps
Rest of the steps are question specific and the reader is encouraged to spend some time and understand them.
Kindly comment below for any further queries or any part which is not clear. I’ll try to explain it further. Here is a link of AC solution for question specific implementation details.
http://codeforces.com/contest/526/submission/11994810
The major idea was that decomposing a tree into various chains based on one special and rest non-special children is useful many a times apart from just HLD.