# Red-blue Trees SOLUTIONS RBTREES

Page Contents

### Red-blue Trees SOLUTIONS RBTREES

In a red-blue tree, every vertex is either red or blue and contiguous vertices consistently have various hues.

You are given a tree with N vertices (numbered 1 through N). It isn’t really a red-blue tree, however its vertices are as yet hued red and blue. You may play out the accompanying activity quite a few times (counting zero): pick two nearby vertices and trade their hues.

Locate the most modest number of tasks needed to change the tree into a red-blue tree or verify that it is inconceivable.

Info

The main line of the info contains a solitary whole number T indicating the quantity of experiments. The depiction of T experiments follows.

The main line of each experiment contains a solitary whole number N. N−1 lines follow. Every one of these lines contains two space-isolated numbers u and v signifying that vertices u and v are associated by an edge.

The last line contains a string S with length N. For each substantial I, the I-th character of this string is either ‘0’ if the I-th vertex is at first red or ‘1’ on the off chance that it is at first blue.

Yield :Print a solitary line containing one whole number ― the most modest number of activities or −1 in the event that it is difficult to change the tree into a red-blue tree.

Requirements

1≤T≤100

1≤N≤100,000

1≤u,v≤N

S contains just characters ‘0’ and ‘1’

the whole of N over all experiments doesn’t surpass 106

Model Input

1 2

1 3

2 4

2 5

3 6

3 7

0010010

Model Output

Clarification

Model case 1: We can play out the accompanying activities:

Trade the shades of vertices 1 and 3; the series of hues becomes “1000010”.

Trade the shades of vertices 1 and 2; the series of hues becomes “0100010”.

Trade the shades of vertices 6 and 3; the series of hues becomes “0110000”, so the tree is a red-blue tree..