AT_arc097_d [ARC097F] Monochrome Cat

有一棵包含 $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 \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 翻译