分数: 800 点
问题陈述
有一棵树 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 =
Wor 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