题目描述

有一棵包含 $N$ 个顶点的树，顶点编号从 $1$ 到 $N$。第 $i$ 条边连接顶点 $x_i$ 和 $y_i$。每个顶点被涂成白色或黑色。顶点 $i$ 的初始颜色由字母 $c_i$ 表示。$c_i$ \= W 表示顶点是白色；$c_i$ \= B 表示顶点是黑色。

一只猫会沿着这棵树走动。具体来说，她每秒钟执行以下操作之一：

• 选择一个与当前所在顶点相邻的顶点，并移动到该顶点。然后，颜色翻转目标顶点。
• 翻转当前所在顶点的颜色。

猫的目标是将所有的顶点都涂成黑色。她可以在任意一个顶点开始和结束行动。至少需要多少秒才能使猫达到目标？

约束条件

• $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

可以在五秒内达到目标，例如：

• 从顶点 $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