#P17535. [JAG 2026 Summer Camp #1] Sliding Puzzle on Tree
[JAG 2026 Summer Camp #1] Sliding Puzzle on Tree
Problem Description
You are given a tree with vertices numbered through . The -th edge of the tree connects vertices and . Initially, for each (), vertex contains one stone if and no stone if .
You can repeatedly perform the following operation:
- Select an unchosen edge with a stone on exactly one of its endpoints, and move that stone to the other endpoint.
Determine whether you can perform the operation exactly times. If possible, output the order in which the edges are selected.
Input Format
The input contains one or more test cases. The first line of the input contains an integer (), which is the number of test cases. The descriptions of the test cases follow, each in the following format.
N
u_1 v_1
u_2 v_2
...
u_{N-1} v_{N-1}
A_1 A_2 ... A_N
The first line contains an integer () representing the number of vertices.
For each (), the -th of the following lines contains two integers and () separated by a space, representing that the -th edge connects vertices and . It is guaranteed that the given graph is a tree.
The last line contains integers () separated by spaces. represents whether a stone is initially placed on vertex .
The sum of over all test cases does not exceed .
Output Format
For each test case, print the answer as follows.
If it is impossible to perform the operation exactly times, output No on a single line.
If it is possible, output Yes on the first line, followed by the sequence of edges on the second line in the following format:
e_1 e_2 ... e_{N-1}
Here, () represents the index of the edge selected in the -th operation. If there are multiple valid sequences, you can output any of them.
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