You are given a tree with n nodes. You are required to color the tree with r colors. Cost of coloring a node with color i is \(A_i\). Also, for each edge, such that the nodes at its end point are colored with the same color i, there is an additional cost of \(B_i\). You are required to find the minimum cost to color all the nodes of the tree.
Input
The first line of the input contains 2 integers n, number of nodes in the tree and r, number of colors.
The second line of the input contains r integers deonting the sequence A.
The third line of the input contains r integers deonting the sequence B.
Each of the next \(n-1\) lines conatins two integers u and v denoting the two nodes which are connected by an edge.
Output
Print one line denoting the minimum cost to color all the nodes in the tree.
Constraints
- \( 1\le n \le 100000\)
- \( 1 \le r \le 1000\)
- \(0 \le A_i, B_i \le 1000000000\)
Color vertex 1 with color 2 (cost = 3)
Color vertices 2 & 3 with color 1 (cost = 2 each).
No additional cost because there is no edge such that both its end points are colored with same color.
Total cost = 3 + 2 + 2 = 7.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor