Problem Description
N children are living in a tree with exactly N nodes, on each node there lies either a boy or a girl.
A girl is said to be protected, if the distance between the girl and her nearest boy is no more than D.
You want to do something good, so that each girl on the tree will be protected. On each step, you can choose two nodes, and swap the children living on them.
What is the minimum number of steps you have to take to fulfill your wish?
Input
The first line has a number T (T <= 150) , indicating the number of test cases.
In a case, the first line contain two number n (1 <= n <= 50), D (1 <= D <= 10000000), Which means the number of the node and the distance between the girls and boys.
The next lines contains n number. The ith number means the ith node contains a girl or a boy. (0 means girl 1 means boy), The follow n - 1 lines contains a, b, w, means a edge connect ath node and bth node, and the length of the edge is w (1 <= w <= 10000000).
Output
For every case, you should output "Case #t: " at first, without quotes. The t is the case number starting from 1.
Then follows the answer, -1 meas you can't comlete it, and others means the minimum number of the times.
Sample Input
1
3 1
0 0 1
1 2 1
1 3 1
Sample Output
Case #1: 1
可也分把这个问题分成两个过程：
第一个过程先遍历case，对每个case运用第二个过程计算最小步数，然后输出结果；
第二个过程主要用来解决每个具体case；
下面我主要讲来一下实现这个算法的思路：
1）根据输入的信息建立两个矩阵和一个常量d，一个矩阵可以描述每个n个节点中对应节点的性别信息，另一个描述任意两节点的距离信息；
就上面的输入而言，可以建立如下两个矩阵：
| 0 0 0 | | 0 1 1 |
G = | 0 0 1 | D = | 1 0 0 |
| 0 0 0 | | 1 0 0 |
矩阵G中每个元素值 G(m,n) 为 1 表示：树中m节点和n节点性别不同，并且 m-n = -1 (否则为0），矩阵D中每个元素 D(m,n) 表示m节点和
n节点的距离。
显然：对树交换m和n节点的性别会改变G矩阵（记作G'） ；
交换性别不会改变边的距离，即不会改变D矩阵。
对D矩阵做一次改变，对任何D(m,n)<=d的元素，令D(m,n) = 0 ，得到的新矩阵记作D'。
现在这个问题就可以这样来描述，最少经过多少步交换可以让G'×D'=零矩阵（×是对应元素的相乘）
2）现在假设G是个N维矩阵，考察交换m和m+1节点的性别会对G产生什么样的改变(1<=m<N).
交换性别的两个节点显然应该满足G(m,m+1)=1，否则说明m和m+1节点性别相同，交换也不会对矩阵 产生任何改变；既然m和m+1节点性别
不同，那么交换之后，G(m-1,m),G(m+1,m+2)的值要改变：
形象地表示在下面这个矩阵中
| 0 |
| 0 |
| 0 |
| 0 |
| 0 (m-1,m) |
| (m,m) (m,m+1) |
| (m+1,m+1) (m+1,m+2) |
| 0 |
| 0 |
| 0 |
可以看出，无论如何交换m节点和m+1节点的性别，也只能影响到主对角线之上那条长为N-1的斜对角线上的值，而上面的N-2维斜三角阵的值
无法通过交换节点性别而改变。
3)最后这个算法的构造应该说是很清楚了，在完成第一阶段的输入后，把G矩阵的N-2维斜三角阵和修改过的D矩阵的N-2维斜三角阵的对应元素
进行比较如果发现有对应元素都不为0，则无论如何交换节点都无法满足问题的要求，输出-1；否则，再做进一步的检查，把上面G矩阵和D'矩阵
的主对角线之上的N-1长的对角线上的元素分别保存在A数组和B数组中，再做进一步的比较。
4)A数组是一个有0和1组成的N-1个元素的数组，对于B数组我们只关心其中不为0的元素的索引，把B数组中不为0的元素的索引保存在C数组中。
A数组中交换两个节点的过程很简单，如果A[m]=1 ，那么改变A[m-1]和A[m+1]的值，0变为1或1变为0。之后就可以和用C对交换后的A矩阵
检查，看看是否C中索引对应的A的元素都为0：
for(i=0;i < C.length;i++)
{
if(!A[C[i]]) return FALSE;
}
当然，对于比较复杂的情况可能在只进行一次交换后仍达不到题目的要求，这个时候需要若干步才能达到要求，然后找出最小步数。
具体的算法我就写了，应该不是特别难想吧
上面那个G矩阵有点问题，因为没有考虑到两个相邻女生出现在最左端或最右端，也没有考虑到3个女生紧靠在一起的情形。
修改G矩阵后大致如下:
1 1 0 0 0 1 0 0 1 0
1 | 1 0 0 0 0 0 0 0 0 0 |
1 | 0 1 1 1 1 0 0 0 0 0 |
0 | 0 1 0 0 0 1 0 0 0 0 |
0 | 0 1 0 0 0 1 0 0 0 0 |
0 | 0 1 0 0 0 1 0 0 0 0 |
1 | 0 0 1 1 1 1 1 1 0 0 |
0 | 0 0 0 0 0 1 0 0 1 0 |
0 | 0 0 0 0 0 1 0 0 1 0 |
1 | 0 0 0 0 0 0 1 1 1 1 |
0 | 0 0 0 0 0 0 0 0 1 0 |
0代表女，1代表男，对角线不全为0，代表对应节点位置的性别，这样比较容易看出关键信息
只取因为矩阵是对称的，只看上三角部分，可以看出矩阵中所有为1的元素是包围连续0的两端为1的元素形成的三角形（三角形定点为0），
形成的这些三角形的顶点记作P1，P2，... ，Pk，这些点唯一决定了当前男生女生在节点中分布的具体情况。
为了表示出包围首尾若干个连续0点的三角形的定点，把原来的N维矩阵扩展至N+2维，现在可以把上面k个顶点表示成：（s1，t1），
（s2，2），（s3，t3），... ，（sk，tk） （其中s1>=0 ,tk<=N+1，tl-sl>=2 ， tl<=sl+1） 注：程序的输入就已经决定了初始的
k个定点
把D矩阵修改一下，让所有小于等于d的位置为0，所有大于d的位置为1，然后再把产生的矩阵凸点处的1改成0，再扩展成N+2维矩阵，
扩充的行列按照紧靠的行和列的值填充，记作 D'
根据输入N个节点的信息可以构造一个N+2长的数组A，0代表女1代表男（A[0]=A[N+1]=1）,连续0若干个0左边和右边第一个1的索引
i ，j 构成了一个三角形的顶点（i，j），有k对，如果经过几次交换后所有顶点满足D'（i，j）= 0 ，就达到题目的要求了