F - Monochrome Cat Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

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

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

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

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

制約

  • 1 ≤ N ≤ 10^5
  • 1 ≤ x_i,y_i ≤ N (1 ≤ i ≤ 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

出力

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

入力例 1

5
1 2
2 3
2 4
4 5
WBBWW

出力例 1

5

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

  • 頂点 1 からはじめる。 頂点 1 の色を黒に変更する。
  • 頂点 2 に移動し、頂点 2 の色を白に変更する。
  • 頂点 2 の色を黒に変更する。
  • 頂点 4 に移動し、頂点 4 の色を黒に変更する。
  • 頂点 5 に移動し、頂点 5 の色を黒に変更する。

入力例 2

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

出力例 2

7

入力例 3

1
B

出力例 3

0

入力例 4

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

出力例 4

21

Score : 800 points

Problem Statement

There is a tree with N vertices numbered 1 through N. The i-th edge connects Vertex x_i and y_i. Each vertex is painted white or black. The initial color of Vertex i is represented by a letter c_i. c_i = W represents the vertex is white; c_i = B represents the vertex is black.

A cat will walk along this tree. More specifically, she performs one of the following in one second repeatedly:

  • Choose a vertex that is adjacent to the vertex where she is currently, and move to that vertex. Then, invert the color of the destination vertex.
  • Invert the color of the vertex where she is currently.

The cat's objective is to paint all the vertices black. She may start and end performing actions at any vertex. At least how many seconds does it takes for the cat to achieve her objective?

Constraints

  • 1 ≤ N ≤ 10^5
  • 1 ≤ x_i,y_i ≤ N (1 ≤ i ≤ N-1)
  • The given graph is a tree.
  • c_i = W or c_i = B.

Input

Input is given from Standard Input in the following format:

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

Output

Print the minimum number of seconds required to achieve the objective.

Sample Input 1

5
1 2
2 3
2 4
4 5
WBBWW

Sample Output 1

5

The objective can be achieved in five seconds, for example, as follows:

  • Start at Vertex 1. Change the color of Vertex 1 to black.
  • Move to Vertex 2, then change the color of Vertex 2 to white.
  • Change the color of Vertex 2 to black.
  • Move to Vertex 4, then change the color of Vertex 4 to black.
  • Move to Vertex 5, then change the color of Vertex 5 to black.

Sample Input 2

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

Sample Output 2

7

Sample Input 3

1
B

Sample Output 3

0

Sample Input 4

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

Sample Output 4

21