Tree Shuffling
Contest: Codeforces Round 646 (Div. 2)
Difficulty rating: 2000
Tags: dfs and similar, dp, greedy, trees

Ashish has a tree consisting of $$$n$$$ nodes numbered $$$1$$$ to $$$n$$$ rooted at node $$$1$$$. The $$$i$$$-th node in the tree has a cost $$$a_i$$$, and binary digit $$$b_i$$$ is written in it. He wants to have binary digit $$$c_i$$$ written in the $$$i$$$-th node in the end.

To achieve this, he can perform the following operation any number of times:

- Select any $$$k$$$ nodes from the subtree of any node $$$u$$$, and shuffle the digits in these nodes as he wishes, incurring a cost of $$$k \cdot a_u$$$. Here, he can choose $$$k$$$ ranging from $$$1$$$ to the size of the subtree of $$$u$$$.

He wants to perform the operations in such a way that every node finally has the digit corresponding to its target.

Help him find the minimum total cost he needs to spend so that after all the operations, every node $$$u$$$ has digit $$$c_u$$$ written in it, or determine that it is impossible.

Input format:
First line contains a single integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ denoting the number of nodes in the tree.

$$$i$$$-th line of the next $$$n$$$ lines contains 3 space-separated integers $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ $$$(1 \leq a_i \leq 10^9, 0 \leq b_i, c_i \leq 1)$$$  — the cost of the $$$i$$$-th node, its initial digit and its goal digit.

Each of the next $$$n - 1$$$ lines contain two integers $$$u$$$, $$$v$$$ $$$(1 \leq u, v \leq n, \text{ } u \ne v)$$$, meaning that there is an edge between nodes $$$u$$$ and $$$v$$$ in the tree.

Output format:
Print the minimum total cost to make every node reach its target digit, and $$$-1$$$ if it is impossible.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The tree corresponding to samples $$$1$$$ and $$$2$$$ are:

In sample $$$1$$$, we can choose node $$$1$$$ and $$$k = 4$$$ for a cost of $$$4 \cdot 1$$$ = $$$4$$$ and select nodes $$${1, 2, 3, 5}$$$, shuffle their digits and get the desired digits in every node.

In sample $$$2$$$, we can choose node $$$1$$$ and $$$k = 2$$$ for a cost of $$$10000 \cdot 2$$$, select nodes $$${1, 5}$$$ and exchange their digits, and similarly, choose node $$$2$$$ and $$$k = 2$$$ for a cost of $$$2000 \cdot 2$$$, select nodes $$${2, 3}$$$ and exchange their digits to get the desired digits in every node.

In sample $$$3$$$, it is impossible to get the desired digits, because there is no node with digit $$$1$$$ initially.

Example input:
5
1 0 1
20 1 0
300 0 1
4000 0 0
50000 1 0
1 2
2 3
2 4
1 5

Example output:
4

Example input:
5
10000 0 1
2000 1 0
300 0 1
40 0 0
1 1 0
1 2
2 3
2 4
1 5

Example output:
24000

Editorial:
Key Idea: Let the parent of node $$$i$$$ be $$$p$$$. If $$$a[i] \geq a[p]$$$, we can do the shuffling which was done at $$$i$$$, at $$$p$$$ instead. Thus, we can do the operation $$$a[i] = min(a[i],a[p])$$$.
Detailed Explanation: Let us denote nodes that have $$$b_i = 1$$$ and $$$c_i = 0$$$ as type $$$1$$$, and those that have $$$b_i = 0$$$ and $$$c_i = 1$$$ as type $$$2$$$. Firstly, the answer is $$$-1$$$ if and only if the number of nodes of type $$$1$$$ and type $$$2$$$ are unequal.
We also observe that only nodes of type $$$1$$$ and $$$2$$$ should be shuffled - it is unoptimal to shuffle those which already have $$$b[i] = c[i]$$$. Thus, we should try to exchange the values of type $$$1$$$ and type $$$2$$$ nodes.
We use the key idea by going down from the root, and at every node $$$i$$$, setting $$$a[i] = min(a[i],a[p])$$$ where $$$p$$$ is the parent node of $$$i$$$ in the tree. Thus, the $$$a[i]$$$'s now follow a special structure: they are non-increasing from the root to the leaves!
This paves the way for our greedy solution: we will go upwards from the leaves, and at each node $$$i$$$ interchange type $$$1$$$ and type $$$2$$$ nodes until we have no nodes in one of these types. Then, we pass on the remaining nodes to the parent to be shuffled.
Time complexity: $$$O(N)$$$