题目描述

頂点に $1$ から $N$ の番号がついた $N$ 頂点からなる木があります。 $i$ 番目の辺は頂点 $x_i$ と $y_i$ を結んでいます。 各頂点は、白か黒のいずれかの色で塗られています。 初期状態では、頂点 $i$ の色は $c_i$ で表されます。 $c_i$ $=$ W のとき 頂点が白いことを、$c_i$ $=$ B のとき 頂点が黒いことを表します。

この木の頂点の上を猫が移動していきます。 具体的には、$1$ 秒間に次の動作のどちらかを行なうことを繰り返します。

• 現在いる頂点と隣接した頂点をひとつ選びその頂点に移動する。その後、移動先の頂点の色を反転する。
• 現在いる頂点の色を反転する。

猫の目標はすべての頂点を黒で塗ることです。どの頂点から動作をはじめても、どの頂点で動作を終えてもかまいません。 最短何秒で目標を達成できるでしょうか?

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $x_1$ $y_1$ $x_2$ $y_2$ $:$ $x_{N-1}$ $y_{N-1}$ $c_1c_2..c_N$

输出格式

目標を達成するために必要な秒数の最小値を出力せよ。

题目大意

给定一棵 $n$ 个节点的树, 每个节点为黑色或白色.

以任意点作为初始位置, 要求进行若干次操作, 使得所有节点变为黑色, 每次操作可选则下面两项中的任意一项执行(记当前位置为 $u$ ):

• 移动到与 $u$ 相邻的某个节点 $v$ , 并反转 $v$ 的颜色.
• 反转 $u$ 的颜色.

求最小的操作次数.

$0 \leq n\leq 10^5$

5
1 2
2 3
2 4
4 5
WBBWW

5

6
3 1
4 5
2 6
6 1
3 4
WWBWBB

7

1
B

0

20
2 19
5 13
6 4
15 6
12 19
13 19
3 11
8 3
3 20
16 13
7 14
3 17
7 8
10 20
11 9
8 18
8 2
10 1
6 13
WBWBWBBWWWBBWWBBBBBW

21

提示

制約

• $1$ $<\ =$ $N$ $<\ =$ $10^5$
• $1$ $<\ =$ $x_i,y_i$ $<\ =$ $N$ ($1$ $<\ =$ $i$ $<\ =$ $N-1$)
• 与えられるグラフは木
• $c_i$ $=$ W または $c_i$ $=$ B

Sample Explanation 1

例えば、次のように行動すると $5$ 秒で達成できます。 - 頂点 $1$ からはじめる。 頂点 $1$ の色を黒に変更する。 - 頂点 $2$ に移動し、頂点 $2$ の色を白に変更する。 - 頂点 $2$ の色を黒に変更する。 - 頂点 $4$ に移動し、頂点 $4$ の色を黒に変更する。 - 頂点 $5$ に移動し、頂点 $5$ の色を黒に変更する。