All submissions for this problem are available.
Flippy the bird has a tree with n nodes. Each edge has a weight wi. We can choose one of the vertices as the root of the tree, say r. Then, the height of the node u would be the sum of the weights on the path from r to u.
Suppose we take the node u as the root. What is the sum of the heights of all nodes? Answer this question for all possible nodes u.
The first line contains a single integer n, the number of nodes of the tree. The next n - 1 lines contain three space-seperated integers, u, v, w, denoting the endpoints of the edge and the weight of the edge respectively.
Output n space-seperated integers. The i-th integer denotes the sum of heights of all vertices if node i is chosen as root.
- 2 ≤ n ≤ 300000
- 1 ≤ wi ≤ 108
- Subtask 1 (28 points) : 2 ≤ n ≤ 5000
- Subtask 2 (72 points) : Original Constraints
Input: 4 1 2 3 2 3 5 2 4 6 Output: 20 14 24 26
Example case. The heights of the nodes when the root is 1 are 0, 3, 8, 9 respectively. So, the sum is 0 + 3 + 8 + 9 = 20. Similarly, you can calculate this value for the case when other nodes are chosen as root as well.
|Tags||easy, tree-dp, zscoder|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||CPP14, JAVA, PYTH, PYTH 3.6, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.