Tree Coloring
Time limit2sMemory limit128 MB
Given a rooted tree with node weights, find the minimum total cost of coloring all nodes in an order that respects parent-before-child, where each node's cost is weight times its coloring position.
- Level
Hard8 of 10
- Topics
- Greedy, Tree, Heap, Union-find
- Solved
- No attempts yet
Problem
A rooted tree has N nodes, and every node has a weight. Let C\[i] be the weight of node i.
You will color all nodes one at a time. If node i is the F\[i]-th node colored, the cost of coloring it is C\[i] * F\[i]. The total cost is the sum of the costs of all nodes.
Before a node can be colored, its parent must already be colored. Therefore, the root must be colored first. Find the minimum possible total cost while following this rule.
Input
The first line contains two integers N and R, the number of nodes in the tree and the root node. (1 ≤ N ≤ 1,000, 1 ≤ R ≤ N)
The second line contains C\[1], C\[2], ..., C\[N] in order.
Each of the next N - 1 lines contains two positive integers U and V. This means that node U is the parent of node V.
Output
Print the minimum total cost needed to color the entire tree.
Hint
If the nodes are colored in the order 1, 3, 5, 2, 4, the step costs are 1 * 1, 2 * 1, 3 * 4, 4 * 2, and 5 * 2, for a total cost of 33.