SP1477 PT07A - Play with a Tree

ACRush 和 Jelly 在进行一场有趣的游戏。游戏规则如下： 在一棵树上，两名玩家轮流切断树上的边。有些节点被认为是“着陆”在地面上的。当某个玩家切掉一条边以后，所有不再与地面相连的边都会被消除。不能再切边的玩家即告失败。 由 ACRush 先手，两人都技术高超。如果你知道这棵树的当前状态，你能否预测谁会赢得比赛？  在此图中，节点 4 在地面上。

输入有多个测试用例。第一行是一个整数 $t$，表示测试用例的数量（$0 < t \leq 20$）。每个测试用例的第一行是一个整数 $N$（$1 \leq N \leq 100000$）。接下来一行包含 $N$ 个整数 $s[i]$（为 $1$ 或 $0$）。如果 $s[i] = 1$，表示第 $i$ 个节点落在地面上；如果 $s[i] = 0$，表示该节点不在地面上。随后有 $N-1$ 行，每行包含两个整数 $u, v$，表示节点 $u$ 和节点 $v$ 之间有一条边（$1 \leq u, v \leq N$）。每个测试用例之间不需要空行分隔。

对于每个测试用例，输出获胜者。如果 ACRush 获胜，输出 `1`；如果是 Jelly 获胜，输出 `0`。同样，每个测试用例的输出之间也不需要空行分隔。

- 测试用例数量 $0 < t \leq 20$ - 节点数量 $1 \leq N \leq 100000$ **本翻译由 AI 自动生成**