Painting Roofs
Time limit2sMemory limit128 MB
Given a tree of houses and M paint costs, assign a color to every house minimizing total cost so that adjacent houses have different colors.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Tree, DFS, Greedy
- Solved
- No attempts yet
Problem
There is a small village with N houses. Roads connect pairs of houses. Using only the given roads, every house can be reached from any other house, and the road network has no cycle; therefore it forms a tree.
Each house's roof must be painted with one color. Two houses directly connected by a road must have different roof colors.
Given the roads between houses and the cost of each paint color, compute the minimum total cost needed to paint all roofs while satisfying the condition.
Input
The first line contains the number of houses, N. The next N-1 lines each contain one road. Each road is described by two different integers A and B between 1 and N, meaning that house A and house B are directly connected.
The next line contains the number of paint colors, M. The final line contains M natural numbers; the i-th number is the cost of painting one house's roof with color i. Every cost is at most 10,000.
Output
Print the minimum total cost required to paint the roofs.
Constraints
- 1 <= N <= 10,000
- 1 <= M <= 10,000