题目描述

有一棵包含 $N$ 个顶点的树，每个顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $x_i$ 和 $y_i$。每个顶点被涂成白色或黑色。初始状态下，顶点 $i$ 的颜色由 $c_i$ 表示。当 $c_i = \text{W}$ 时，表示顶点为白色；当 $c_i = \text{B}$ 时，表示顶点为黑色。

有一只猫在树的顶点上移动。具体来说，每 $1$ 秒可以重复执行以下两种操作之一：

• 选择当前所在顶点的一个相邻顶点，移动到该顶点，并将移动到的顶点颜色反转。
• 将当前所在顶点的颜色反转。

猫的目标是将所有顶点都涂成黑色。可以从任意顶点开始，也可以在任意顶点结束。请问，最少需要多少秒才能达成目标？

输入格式

输入以如下格式从标准输入读入：

$N$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_{N-1}$ $y_{N-1}$
$c_1c_2\ldots c_N$

输出格式

输出达成目标所需的最小秒数。

样例 1

输入

5
1 2
2 3
2 4
4 5
WBBWW

输出

5

样例 2

输入

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

输出

7

样例 3

输入

1
B

输出

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

输出

21

说明/提示

限制条件

• $1 \leq N \leq 10^5$
• $1 \leq x_i, y_i \leq N$ （$1 \leq i \leq N-1$）
• 给定的图是一棵树
• $c_i = \text{W}$ 或 $c_i = \text{B}$

样例解释 1

例如，按照如下方式行动可以在 $5$ 秒内达成目标：

• 从顶点 $1$ 开始，将顶点 $1$ 的颜色变为黑色。
• 移动到顶点 $2$，将顶点 $2$ 的颜色变为白色。
• 将顶点 $2$ 的颜色变为黑色。
• 移动到顶点 $4$，将顶点 $4$ 的颜色变为黑色。
• 移动到顶点 $5$，将顶点 $5$ 的颜色变为黑色。

由 ChatGPT 4.1 翻译