#P17535. [JAG 2026 Summer Camp #1] Sliding Puzzle on Tree
[JAG 2026 Summer Camp #1] Sliding Puzzle on Tree
题目描述
给定一棵有 个顶点的树,顶点编号为 到 。树的第 条边连接顶点 和 。初始时,对于每个 (),若 ,则顶点 上有一块石子;若 ,则该顶点上没有石子。
你可以重复执行以下操作:
- 选择一条此前没有选择过的边,要求它的两个端点中恰好有一个端点上有石子,然后将该石子移动到另一个端点。
判断是否能恰好执行 次操作。如果可以,输出选择各条边的顺序。
输入格式
输入包含一组或多组测试数据。第一行包含一个整数 (),表示测试数据组数。接下来给出 组测试数据,每组格式如下:
N
u_1 v_1
u_2 v_2
...
u_{N-1} v_{N-1}
A_1 A_2 ... A_N
第一行包含一个整数 (),表示顶点数量。
对于每个 (),接下来 行中的第 行包含两个用空格分隔的整数 和 (),表示第 条边连接顶点 和 。保证给定图是一棵树。
最后一行包含 个用空格分隔的整数 ()。 表示顶点 上初始时是否放有石子。
所有测试数据的 之和不超过 。
输出格式
对于每组测试数据,按以下方式输出答案。
若无法恰好执行 次操作,在单独一行输出 No。
若可以,第一行输出 Yes,第二行按以下格式输出边的序列:
e_1 e_2 ... e_{N-1}
这里,()表示第 次操作所选择的边的编号。若存在多个合法序列,可以输出其中任意一个。
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