给你一棵由 $$$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$$$。