CF2119F.Volcanic Eruptions

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

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

题目描述

有一棵以 $1$ 号点为根的无向树，每个顶点有一个权值 $w_i\in\{1,-1\}$ 。

根节点的火山在时间 $0$ 爆发。在时间 $t$ 时，距离根节点不超过 $t$ 的所有顶点都会被岩浆淹没，其中距离指的是两点之间最短路径上的边数。

在时间 $0$ ，你位于顶点 $st$ ，生命值 $S$ 为 $1$ 。从时间 $0$ 开始（包括时间 $0$ ），每个时间点依次发生以下事件：

设你当前所在的顶点为 $u$ ，你的生命值增加 $w_u$ ，即 $S\gets S+w_u$ 。
如果 $S=0$ ，或者顶点 $u$ 在此时被岩浆淹没，则你立即死亡。
你必须移动到一个相邻的顶点（包括父节点和子节点，不能原地停留）。你将在下一个时间点到达所选顶点。

请你求出在你死亡前最多能移动多少步。

输入格式

每组测试数据包含多组测试用例。第一行包含一个整数 $T$ （ $1\le T\le 10^4$ ），表示测试用例的组数。

对于每组测试用例，第一行包含两个整数 $n,st$ （ $2\le st\le n\le 5\times 10^5$ ），表示树的顶点数和你在时间 $0$ 时所在的顶点编号。

第二行包含 $n$ 个整数 $w_1, w_2, \ldots, w_n$ （ $w_i\in\{1,-1\}$ ， $w_{st}=1$ ），表示每个顶点的权值。

接下来 $n-1$ 行，每行包含两个整数 $u,v$ （ $1\le u,v\le n$ ），表示一条连接顶点 $u$ 和 $v$ 的边。

保证给定的图是一棵树，且所有测试用例中 $n$ 的总和不超过 $10^6$ 。

输出格式

对于每组测试用例，输出一行一个整数，表示你在死亡前最多能移动的步数。

输入输出样例

输入#1

6
7 4
-1 -1 -1 1 1 1 -1
2 1
3 2
4 3
5 4
6 5
7 6
8 2
-1 1 1 1 1 -1 1 1
2 1
6 2
8 6
3 8
7 3
5 7
4 5
8 2
-1 1 -1 -1 -1 1 -1 -1
2 1
8 2
4 1
5 4
3 4
7 2
6 8
8 4
1 1 1 1 1 -1 1 -1
8 1
3 1
4 3
5 4
6 4
7 6
2 5
8 4
1 1 1 1 -1 -1 1 1
2 1
5 1
4 5
8 5
3 8
7 2
6 2
18 10
-1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 1 -1 1 1 1 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
9 14
14 15
15 16
16 17
17 18

输出#1

说明/提示

下图展示了第一个测试用例中的树结构。

第一个测试用例中，一种最优的移动序列为 $4\to3\to4\to5\to6\to7\to6$ ，共移动 $6$ 步。生命值 $S$ 的变化为 $2\to1\to2\to3\to4\to3\to4$ 。具体过程如下：

时间 $0$ ，生命值 $S$ 变为 $2$ ，从顶点 $4$ 移动到顶点 $3$ 。
时间 $1$ ，生命值 $S$ 变为 $1$ ，从顶点 $3$ 移动到顶点 $4$ 。
时间 $2$ ，生命值 $S$ 变为 $2$ ，从顶点 $4$ 移动到顶点 $5$ 。
时间 $3$ ，生命值 $S$ 变为 $3$ ，从顶点 $5$ 移动到顶点 $6$ 。
时间 $4$ ，生命值 $S$ 变为 $4$ ，从顶点 $6$ 移动到顶点 $7$ 。
时间 $5$ ，生命值 $S$ 变为 $3$ ，顶点 $7$ 到根的距离为 $6$ ，尚未被岩浆淹没。从顶点 $7$ 移动到顶点 $6$ 。
时间 $6$ ，生命值 $S$ 变为 $4$ ，但顶点 $6$ 到根的距离为 $5$ ，此时被岩浆淹没。

由 ChatGPT 4.1 翻译

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

首页