← 返回题目列表

Codeforces · 1910/J

J. 两种颜色

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

给你一棵由 $$$n$$$ 个顶点组成的树。树的一些顶点是红色的,所有其他顶点是蓝色的。

树的每条边都有一个正权重。让我们将 $$$d(x, y)$$$ 定义为顶点 $$$x$$$ 和 $$$y$$$ 之间的距离,i。 e.属于 $$$x$$$ 和 $$$y$$$ 之间简单路径的边的权重总和。

对于每个顶点,您必须选择一个整数 $$$v_i$$$。这些整数应满足以下约束:对于每个蓝色顶点 $$$b$$$ 和每个红色顶点 $$$r$$$,$$$d(b, r) \ge v_b + v_r$$$。

你必须最大化 $$$\sum \limits_{i=1}^{n} v_i$$$ 的值。

请注意,$$$v_i$$$ 的值不一定是正数。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$c_1, c_2, \dots, c_n$$$ ($$$0 \le c_i \le 1$$$)。如果第 $$$i$$$ 个顶点为红色,则 $$$c_i = 1$$$,否则 $$$c_i = 0$$$。

然后是 $$$n-1$$$ 行。每行包含三个整数 $$$x_i$$$、$$$y_i$$$ 和 $$$w_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$1 \le w_i \le 10^6$$$; $$$x_i \ne y_i$$$) 表示顶点 $$$x_i$$$ 和$$$y_i$$$ 的权重为 $$$w_i$$$。这些边形成一棵树。

输出

如果 $$$\sum \limits_{i=1}^{n} v_i$$$ 的值可以尽可能大,则打印 Infinity。否则,打印一个整数 - 您可以获得的 $$$\sum \limits_{i=1}^{n} v_i$$$ 的最大可能值。

示例

输入 #1

4
1 1 0 0
3 4 50
3 2 100
2 1 100

输出 #1

350

输入 #2

6
0 1 0 1 0 1
1 2 1
1 4 1
1 6 1
6 5 100
6 3 100

输出 #2

203

输入 #3

3
1 1 1
1 2 100
2 3 100

输出 #3

Infinity

注意

在第一个示例中,您可以指定 $$$v_1 = 120、v_2 = 20、v_3 = 80、v_4 = 130$$$。