有一个无向树,根为 $$$1$$$,其中每个顶点的权重为 $$$w_i\in\{1,-1\}$$$。
根部的一座火山在时间 $$$0$$$ 喷发。在时间 $$$t$$$ 时,熔岩淹没了距根部距离至多 $$$t$$$ 的所有顶点,其中距离是两个顶点之间最短路径中的边数。
在时间$$$0$$$,你处于顶点$$$st$$$,生命值为$$$S$$$,最初$$$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\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$$$。
输出
对于每个测试用例,输出一行,其中包含一个整数,指示您可以进行的最大移动次数。
示例
输入复制
67 4-1 -1 -1 1 1 1 -12 13 24 35 46 57 68 2-1 1 1 1 1 -1 1 12 16 28 63 87 35 74 58 2-1 1 -1 -1 -1 1 -1 -12 18 24 15 43 47 26 88 41 1 1 1 1 -1 1 -18 13 14 35 46 47 62 58 41 1 1 1 -1 -1 1 12 15 14 58 53 87 26 218 10-1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 1 -1 1 1 1 11 22 33 44 55 66 77 88 99 1010 1111 1212 139 1414 1515 1616 1717 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$$$被熔岩淹没。