CF1363E.Tree Shuffling

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.

阿什什有一棵由 $n$ 个节点组成的树，节点编号为 $1$ 到 $n$，根节点为节点 $1$。树中第 $i$ 个节点有一个代价 $a_i$，且写有一个二进制数字 $b_i$。他希望最终第 $i$ 个节点上写的二进制数字为 $c_i$。

为实现这一目标，他可以执行以下操作任意多次：

• 任选节点 $u$ 的子树中的任意 $k$ 个节点，并随意重排这些节点上的二进制数字，该操作花费代价为 $k \cdot a_u$。其中，$k$ 可取 $1$ 到 $u$ 的子树大小之间的任意整数。

他希望以某种方式执行这些操作，使得每个节点最终所写的数字均与其目标值一致。

请帮助他求出使所有节点 $u$ 最终写有数字 $c_u$ 所需的最小总代价；若不可能实现，则判定其不可行。

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.

第一行包含一个整数 $n$ $(1 \le n \le 2 \cdot 10^5)$，表示树中节点的数量。

接下来的 $n$ 行中，第 $i$ 行包含三个用空格分隔的整数 $a_i$、$b_i$、$c_i$ $(1 \leq a_i \leq 10^9, 0 \leq b_i, c_i \leq 1)$ —— 分别表示第 $i$ 个节点的代价、其初始数字和目标数字。

接下来的 $n - 1$ 行中，每行包含两个整数 $u$、$v$ $(1 \leq u, v \leq n, \text{ } u \ne v)$，表示树中节点 $u$ 与节点 $v$ 之间存在一条边。

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

输出使每个节点都达到其目标数字的最小总代价；如果无法实现，则输出 $-1$。

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.

对应样例 $1$ 和样例 $2$ 的树如下：

在样例 $1$ 中，我们可以选择节点 $1$ 并取 $k = 4$，花费为 $4 \cdot 1 = 4$，选中节点集 $\{1, 2, 3, 5\}$，对其数字进行重排，从而使得每个节点均得到目标数字。

在样例 $2$ 中，我们可以选择节点 $1$ 并取 $k = 2$，花费为 $10000 \cdot 2$，选中节点集 $\{1, 5\}$ 并交换它们的数字；类似地，选择节点 $2$ 并取 $k = 2$，花费为 $2000 \cdot 2$，选中节点集 $\{2, 3\}$ 并交换它们的数字，从而使得每个节点均得到目标数字。

在样例 $3$ 中，无法得到目标数字，因为初始时没有任何节点包含数字 $1$。