火山喷发

• 每次测试时间限制为$3$秒
• 每次测试内存限制为$256$兆字节

题目描述

存在一棵无向树，根节点为$1$。
每个顶点都有权重 $w_i \in \{1, -1\}$。

火山根部有时会喷发。
在时刻 $t$，熔岩淹没了所有距离根节点不超过 $t$ 的顶点，其中距离是两个顶点之间最短路径中的边数。

在时刻 $0$，你处于顶点 $s_t$，具有生命值 $S$，最初 $S = 1$。
时间从 $0$ 开始（包括时间 $0$），以下事件在每个时间戳按顺序发生：

1. 设 $u$ 为你现在所在的顶点。你的生命值会增加 $w_u$，即 $S \leftarrow S + w_u$。
2. 如果 $S = 0$ 或者顶点 $u$ 此时被熔岩淹没，你会立刻死亡。
3. 你必须移动到相邻的顶点（包括父子；不允许原地停留）。你会在下一个时间戳到达选定的顶点。

找出你死前能做的最大动作数。

输入格式

每个测试包含多个测试用例。
第一行包含测试用例的数量 $T$（$1 \le T \le 10^4$）。
接下来是每个测试用例的描述。

对于每个测试用例：

• 第一行包含两个整数 $n, s$（$2 \le t \le n \le 5 \cdot 10^5$），表示顶点数和你在时间戳 $0$ 时起始的顶点。
• 第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$（$w_i \in \{1, -1\}$，且 $w_s = 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 \to 3 \to 4 \to 5 \to 6 \to 7 \to 6$，共 $6$ 次移动。
生命值 $S$ 的变化为：$2 \to 1 \to 2 \to 3 \to 4 \to 3 \to 4$。更准确地说：

• 在时刻 $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$ 被熔岩淹没。