← 返回题目列表

Codeforces · 1363/E

E. 树洗牌

中文机器翻译题面 查看原题

Ashish 有一个由 $$$n$$$ 节点组成的树,编号为 $$$1$$$ 到 $$$n$$$,根节点为 $$$1$$$。树中第$$$i$$$个节点的成本为$$$a_i$$$,其中写入二进制数字$$$b_i$$$。他希望最后在第$$$i$$$个节点中写入二进制数字$$$c_i$$$。

为此,他可以执行以下操作任意多次:

- 从任意节点$$$u$$$的子树中选择任意$$$k$$$节点,并按照他的意愿对这些节点中的数字进行打乱,产生$$$k \cdot a_u$$$的成本。这里,他可以选择$$$k$$$,范围从$$$1$$$到$$$u$$$子树的大小。

他希望以这样的方式执行操作,使得每个节点最终都有与其目标对应的数字。

帮助他找到他需要花费的最小总成本,使得在所有操作之后,每个节点 $$$u$$$ 都写入数字$$$c_u$$$,或者确定这是不可能的。

输入

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

接下来的 $$$n$$$ 行中的第 $$$i$$$ 行包含 3 个空格分隔的整数 $$$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$$$ 之间有一条边。

输出

打印使每个节点达到目标数字的最小总成本,如果不可能,则打印$$$-1$$$。

示例

输入 #1

5
1 0 1
20 1 0
300 0 1
4000 0 0
50000 1 0
1 2
2 3
2 4
1 5

输出 #1

4

输入 #2

5
10000 0 1
2000 1 0
300 0 1
40 0 0
1 1 0
1 2
2 3
2 4
1 5

输出 #2

24000

输入 #3

2
109 0 1
205 0 1
1 2

输出 #3

-1

注意

样本$$$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$$$的节点。