← 返回题目列表

AtCoder · arc097_d

F. 单色猫

中文机器翻译题面 查看原题

分数: 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 = W or 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