21614_Tree

Given a tree with n nodes, each of which is colored black or white, you are allowed to swap any two nodes at a time, now your task is to make those black nodes connected to each other, using as few swaps as possible.

Input may contain several test cases. The first line is a positive integer T, the number of test cases below. For each test case, the first line is a positive integer n, ( 1 ≤ n ≤ 100 ) the number of nodes in the tree. The nodes are numbered from 1 to n. The second line consists of n letters ( 'b' or 'w' ) separated by spaces, denoting the color of node 1, 2, ..., n. From the 3rd line to the n+2-th line are the descriptions of n-1 edges in the tree. Each line contains two integer x, y, ( 1 ≤ x, y ≤ n ), denoting edge (x, y)

For each test case, output the minimum number of swaps to make black nodes connected to each other.

1
4
b b b w
1 4
2 4
3 4

1