← 返回题目列表

Codeforces · 2119/F

F. 火山喷发

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

有一个无向树,根为 $$$1$$$,其中每个顶点的权重为 $$$w_i\in\{1,-1\}$$$。

根部的一座火山在时间 $$$0$$$ 喷发。在时间 $$$t$$$ 时,熔岩淹没了距根部距离至多 $$$t$$$ 的所有顶点,其中距离是两个顶点之间最短路径中的边数。

在时间$$$0$$$,你处于顶点$$$st$$$,生命值为$$$S$$$,最初$$$S=1$$$。从时间$$$0$$$开始(包括时间$$$0$$$),以下事件在每个时间戳处按顺序发生:

  1. 设 $$$u$$$ 为您当前所在的顶点。你的生命值增加$$$w_u$$$,即$$$S\gets S+w_u$$$。
  2. 如果$$$S=0$$$或者此时顶点$$$u$$$被熔岩淹没,你会立即死亡。
  3. 你 必须 移动到相邻的顶点(包括父亲和儿子;不允许留在原地)。您将在下一个时间戳到达所选顶点。

找出你死前可以进行的最大移动次数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$T$$$ ($$$1 \le T \le 10^4$$$)。测试用例的描述如下。

对于每个测试用例,第一行包含两个整数 $$$n,st$$$ ($$$2 \le st \le n \le 5\cdot 10^5$$$),表示顶点数以及从时间戳 $$$0$$$ 开始的顶点。

第二行包含 $$$n$$$ 整数 $$$w_1, w_2, \ldots, w_n$$$ ($$$w_i\in\{1,-1\}$$$,$$$w_{st}=1$$$),其中 $$$w_i$$$ 表示顶点 $$$i$$$ 的权重。

接下来的 $$$n-1$$$ 行每行包含两个整数 $$$u,v$$$ ($$$1\le u,v \le n$$$),它们描述由边连接的一对顶点。

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

输出

对于每个测试用例,输出一行,其中包含一个整数,指示您可以进行的最大移动次数。

示例

输入
复制

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

输出
复制

6
7
3
3
1
13

注意

这是显示第一个测试用例中的树的图片。

第一个测试用例。

最佳移动顺序之一是 $$$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$$$还没有被熔岩淹没。我们从顶点 $$$7$$$ 移动到顶点 $$$6$$$。
  • 在$$$6$$$时刻,生命值$$$S$$$变为$$$4$$$,但顶点$$$6$$$到根的距离为$$$5$$$,这意味着顶点$$$6$$$被熔岩淹没。