33OJ
登录 注册

#P17535. [JAG 2026 Summer Camp #1] Sliding Puzzle on Tree

[JAG 2026 Summer Camp #1] Sliding Puzzle on Tree

题目描述

给定一棵有 NN 个顶点的树,顶点编号为 11 到 NN。树的第 ii 条边连接顶点 uiu_i 和 viv_i。初始时,对于每个 ii(1≤i≤N1\le i\le N),若 Ai=1A_i=1,则顶点 ii 上有一块石子;若 Ai=0A_i=0,则该顶点上没有石子。

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

  • 选择一条此前没有选择过的边,要求它的两个端点中恰好有一个端点上有石子,然后将该石子移动到另一个端点。

判断是否能恰好执行 N−1N-1 次操作。如果可以,输出选择各条边的顺序。

输入格式

输入包含一组或多组测试数据。第一行包含一个整数 TT(1≤T≤1051\le T\le 10^5),表示测试数据组数。接下来给出 TT 组测试数据,每组格式如下:

N
u_1 v_1
u_2 v_2
...
u_{N-1} v_{N-1}
A_1 A_2 ... A_N

第一行包含一个整数 NN(2≤N≤2×1052\le N\le 2\times 10^5),表示顶点数量。

对于每个 ii(1≤i≤N−11\le i\le N-1),接下来 N−1N-1 行中的第 ii 行包含两个用空格分隔的整数 uiu_i 和 viv_i(1≤ui,vi≤N1\le u_i,v_i\le N),表示第 ii 条边连接顶点 uiu_i 和 viv_i。保证给定图是一棵树。

最后一行包含 NN 个用空格分隔的整数 A1,A2,…,ANA_1,A_2,\ldots,A_N(Ai∈{0,1}A_i\in\{0,1\})。AiA_i 表示顶点 ii 上初始时是否放有石子。

所有测试数据的 NN 之和不超过 2×1052\times 10^5。

输出格式

对于每组测试数据,按以下方式输出答案。

若无法恰好执行 N−1N-1 次操作,在单独一行输出 No。

若可以,第一行输出 Yes,第二行按以下格式输出边的序列:

e_1 e_2 ... e_{N-1}

这里,eke_k(1≤ek≤N−11\le e_k\le N-1)表示第 kk 次操作所选择的边的编号。若存在多个合法序列,可以输出其中任意一个。

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