CF2119F Volcanic Eruptions

有一棵以 $1$ 号点为根的无向树，每个顶点有一个权值 $w_i\in\{1,-1\}$。 根节点的火山在时间 $0$ 爆发。在时间 $t$ 时，距离根节点不超过 $t$ 的所有顶点都会被岩浆淹没，其中距离指的是两点之间最短路径上的边数。 在时间 $0$，你位于顶点 $st$，生命值 $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\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$。

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

下图展示了第一个测试用例中的树结构。  第一个测试用例中，一种最优的移动序列为 $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 翻译