Red and Black Tree

题意翻译

### 题目描述 给出一棵 $n$ 个节点的树，树上的节点有红黑两种颜色。每次操作可以交换两个节点的颜色，问最少需要多少次操作可以使得树上任意一个点均存在与它距离 $\leq x$ 的黑点，在这里认为树上两个节点的距离为它们之间的最短路径长度。 ### 输入格式 第一行两个整数 $n,x (2 \leq n \leq 500 , 1 \leq x \leq 10^9)$。 第二行 $n$ 个整数，第 $i$ 个整数描述 $i$ 点的颜色，如果为 $1$ 则其为黑色，如果为 $0$ 则其为红色。 接下来 $n-1$ 行每行三个整数 $u_i,v_i,w_i(1 \leq u_i,v_i \leq n,u_i \leq v_i,1 \leq w_i \leq 10^9)$ 描述树上一条连接 $u_i$ 和 $v_i$ 的权值为 $w_i$ 的边。 ### 输出格式 一行一个整数，如果无论如何操作都无法满足条件输出 `-1`，否则输出最小的操作次数。

题目描述

You have a weighted tree, consisting of $ n $ vertices. Each vertex is either painted black or is painted red. A red and black tree is called beautiful, if for any its vertex we can find a black vertex at distance at most $ x $ . The distance between two nodes is the shortest path between them. You have a red and black tree. Your task is to make it beautiful in the minimum number of color swap operations. In one color swap operation, you can choose two vertices of different colors and paint each of them the other color. In other words, if you choose a red vertex $ p $ and a black vertex $ q $ , then in one operation you are allowed to paint $ p $ black and paint $ q $ red. Print the minimum number of required actions.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ x $ $ (2<=n<=500; 1<=x<=10^{9}) $ . The next line contains $ n $ integers, each of them is either a zero or one. If the $ i $ -th number equals 1, then vertex $ i $ of the tree is black, otherwise vertex $ i $ is red. Next $ n-1 $ lines contain the tree edges. The $ j $ -th line contains integers $ u_{j} v_{j} w_{j} $ $ (1<=u_{j},v_{j}<=n; u_{j}≠v_{j}; 1<=w_{j}<=10^{9}) $ which means that the tree has an edge of weight $ w_{j} $ between vertices $ v_{j} $ and $ u_{j} $ . Assume that the tree vertices are numbered from 1 to $ n $ .

输出格式

Print a single integer — the minimum number of required swap operations. If it is impossible to get a beautiful tree at any number of operations, print -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