配点 : $800$ 点

問題文

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

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

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

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

制約

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

入力

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

$N$

$x_1$ $y_1$

$x_2$ $y_2$

$:$

$x_{N-1}$ $y_{N-1}$

$c_1c_2..c_N$

出力

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

5
1 2
2 3
2 4
4 5
WBBWW

5

例えば、次のように行動すると $5$ 秒で達成できます。

• 頂点 $1$ からはじめる。 頂点 $1$ の色を黒に変更する。
• 頂点 $2$ に移動し、頂点 $2$ の色を白に変更する。
• 頂点 $2$ の色を黒に変更する。
• 頂点 $4$ に移動し、頂点 $4$ の色を黒に変更する。
• 頂点 $5$ に移動し、頂点 $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