[ARC097F] Monochrome Cat

给定一棵 $n$ 个节点的树, 每个节点为黑色或白色. 以任意点作为初始位置, 要求进行若干次操作, 使得所有节点变为黑色, 每次操作可选则下面两项中的任意一项执行(记当前位置为 $u$ ): - 移动到与 $u$ 相邻的某个节点 $v$ , 并反转 $v$ 的颜色. - 反转 $u$ 的颜色. 求最小的操作次数. $0 \leq n\leq 10^5$

[problemUrl]: https://atcoder.jp/contests/arc097/tasks/arc097_d 頂点に $ 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 $

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

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 $ の色を黒に変更する。