← 返回题目列表

Codeforces · 375/E

E. 红黑树

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

您有一个由 n 个顶点组成的加权树。每个顶点要么涂成黑色,要么涂成红色。一棵红黑树被称为美丽的,如果对于它的任何顶点我们可以在距离不超过 x 处找到一个黑色顶点。

两个节点之间的距离是它们之间的最短路径。

你有一棵红黑树。你的任务是用最少的颜色交换操作让它变得漂亮。在一个颜色交换操作中,您可以选择不同颜色的两个顶点并将它们分别绘制为另一种颜色。换句话说,如果您选择红色顶点 p 和黑色顶点 q,则在一次操作中您可以将 p 涂成黑色,将 q 涂成红色。

打印所需操作的最少数量。

输入

第一行包含两个整数 n 和 x (2 ≤ n ≤ 500; 1 ≤ x ≤ 109)。下一行包含 n 个整数,每个整数不是零就是一。如果第 i 个数等于 1,则树的顶点 i 为黑色,否则顶点 i 为红色。接下来的 n - 1 行包含树的边缘。第 j 行包含整数 uj vj wj (1 ≤ uj, vj ≤ n; uj ≠ vj; 1 ≤ wj ≤ 109),这意味着树在顶点 vj 和 uj 之间有一条权重为 wj 的边。

假设树顶点编号为 1 到 n。

输出

打印单个整数 — 所需交换操作的最小数量。

如果通过任意次数的操作都不可能得到一棵美丽的树,则打印 -1。

示例

输入 #1

3 2
1 0 0
1 2 2
2 3 2

输出 #1

1

输入 #2

4 2
0 1 0 0
1 2 2
2 3 2
3 4 2

输出 #2

-1