Hussain Kara FallahACM ICPC Contestant, Coach, Judge, Problem Setter. IOI 2014. · 3y
Hint 1:
This problem is an interesting exercise on centroid decomposition. In fact it's one of the earliest problems which appeared involving centroid decomposition before it become a popular algorithm in CP contests. If you are not familiar with centroid decomposition you better refer to this tutorial Centroid Decomposition in Trees Tutorial , after that you should solve this simple problem Codeforces 321C: Ciel The Commander . After that you should be able to understand the solution.
Hint 2:
After finding the centroid of our tree, if we process all paths passing by this centroid, then we would be able to remove this centroid and break our tree into smaller independent subtrees (each with size not exceeding half of our big tree's size). After that we can solve each of our small subtrees independently.
Hint 3:
Now let's tell about processing all paths passing by a fixed centroid. First of all let's consider all children of our centroid (of course without ones that had been processed as centroids, because we found all paths passing by them, and doing that again would count duplicates and may also lead to TLE). Consider our centroid children (c1,c2,c3,c4..ck). Any simple path passing by the centroid would be a union of 2 paths ({centroid->v} , {centroid->u} ). where (v,u) are 2 nodes belonging to 2 different subtrees rooted at 2 different children of our centroid. If they belong to the subtree rooted at the same centroid's child, then the path won't be simple.
Hint 4:
Let's process the centroid's children subtrees one by one. For each of them we call a DFS starting from the centroid to this subtree nodes. For each path from the centroid to a node belonging to this subtree, we should calculate the weight of this path, and the number of edges forming this path. If our path's weight is equal to x then it should be joined with another path starting at the centroid with total weight K-x, and of course formed with minimum number of edges.
Hint 5:
We should maintain an array E[K]. E[i] represents the minimum number of edges forming a path of weight i (among all processed paths before). So for each subtree we should first try to join paths to nodes in this subtree with previous results. After that we may add them to our array E[]. After finishing each centroid we should reset our array E[]. Check my implementation for details.
Read more… (407 words)