AT_arc097_d.[ARC097F] Monochrome Cat

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一棵包含 $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
```
输出#1
```
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

说明/提示

限制条件

$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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页