Tomorrow is Kerry’s birthday. Jim is planning to gift her a rooted tree with n nodes. Nodes are numbered from 1 to n, rooted at node 1. Every node has a cost associated with it and a color either black or white. It’s been years and Jim know exactly what combination of colors Kerry will love. So, he knows which target color (Black/White) every node should have at the end. To do so, he can perform the following operation any number of times: Select any node p except a leaf node, and swap colors of any two nodes in the subtree of node p. This operation costs equal to the cost associated with the node p. He wants that after performing such operations every node finally has the color corresponding to its target. Help him find out the minimum total cost for such operations after which every node has the corresponding target color, or find out if that is impossible.
Answers
Explanation:
Tomorrow is Kerry’s birthday. Jim is planning to gift her a rooted tree with n nodes. Nodes are numbered from 1 to n, rooted at node 1. Every node has a cost associated with it and a color either black or white. It’s been years and Jim know exactly what combination of colors Kerry will love. So, he knows which target color (Black/White) every node should have at the end.
To do so, he can perform the following operation any number of times:
Select any node p except a leaf node, and swap colors of any two nodes in the subtree of node p. This operation costs equal to the cost associated with the node p.
He wants that after performing such operations every node finally has the color corresponding to its target.
Help him find out the minimum total cost for such operations after which every node has the corresponding target color, or find out if that is impossible.
Input Format
First line contains a single integer n, the numbers of nodes in the tree (1 ≤ n ≤ 105).
ith line of the next n lines contain 3 space-separated integers Ci, Ui, Ti, denoting the cost of ith node, the initial color of ith node, and target color of ith node respectively. 0 represent white color and 1 represent black color. (1 ≤ Ci ≤ 109, 0 ≤ Ui ≤ 1, 0 ≤ Ti ≤ 1).
Next n-1 lines contain 2 space-separated integers x, y (1 ≤ x ≤ n, 1 ≤ y ≤ n, x != y), meaning that there is an edge between x and y.
It is guaranteed that given edges will constitute a tree.
Output Format
Print a single integer denoted minimum total cost as described, or -1 if it is not possible.
Sample Testcase #0
Testcase Input
4
10 0 0
20 1 0
30 0 1
40 1 1
4 1
2 3
1 3
Testcase Output
10
Explanation
If we swap node 2 and node 3, every node color will be same as corresponding target color.
Node 2 and node 3 both are in Subtree of node 3 and Subtree of node 1. If we choose subtree of node 3 then cost will be 30, while if we choose subtree of node 1 then cost will be 10 only.
Hence output is 10.