树上滑块谜题 - Problem

给定一棵包含 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。树的第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。初始时，对于每个 $i$（$1 \le i \le N$），若顶点 $i$ 满足 $A_i = 1$，则其上有一颗石子；若 $A_i = 0$，则没有石子。

你可以重复执行以下操作：

请判断是否能够恰好执行 $N - 1$ 次操作。如果可以，请输出选择边的顺序。

输入包含一个或多个测试用例。输入的第一行包含一个整数 $T$（$1 \le T \le 10^5$），表示测试用例的数量。接下来是 $T$ 个测试用例的描述，每个测试用例的格式如下。

$$ \begin{aligned} &N \\ &u_1 \ v_1 \\ &u_2 \ v_2 \\ &\vdots \\ &u_{N-1} \ v_{N-1} \\ &A_1 \ A_2 \ \ldots \ A_N \end{aligned} $$

第一行包含一个整数 $N$（$2 \le N \le 2 \times 10^5$），表示顶点的数量。

对于每个 $i$（$1 \le i \le N - 1$），接下来的第 $i$ 行（共 $N - 1$ 行）包含两个由空格分隔的整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le N$），表示第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。保证给定的图是一棵树。

最后一行包含 $N$ 个由空格分隔的整数 $A_1, A_2, \ldots, A_N$（$A_i \in \{0, 1\}$）。$A_i$ 表示初始时顶点 $i$ 上是否放有石子。

所有测试用例的 $N$ 之和不超过 $2 \times 10^5$。

对于每个测试用例，按如下格式输出答案。

如果无法恰好执行 $N - 1$ 次操作，则在一行中输出 No。

如果可以，则在第一行输出 Yes，接着在第二行按如下格式输出边的序列：

$$ e_1 \ e_2 \ \ldots \ e_{N-1} $$

其中，$e_k$（$1 \le e_k \le N - 1$）表示第 $k$ 次操作中所选择的边的编号。如果存在多个合法的序列，输出任意一个即可。

3
5
1 2
2 3
2 4
2 5
1 1 1 0 0
2
1 2
0 0
9
1 2
2 3
2 4
4 5
4 6
6 7
6 8
6 9
0 0 1 0 1 1 0 1 1

Yes
3 2 4 1
No
Yes
6 7 4 2 1 3 5 8

QOJ.ac