33OJ
登录 注册

#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 NN vertices numbered 11 through NN. The ii-th edge of the tree connects vertices uiu_i and viv_i. Initially, for each ii (1≤i≤N1\le i\le N), vertex ii contains one stone if Ai=1A_i=1 and no stone if Ai=0A_i=0.

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 N−1N-1 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 TT (1≤T≤1051\le T\le 10^5), which is the number of test cases. The descriptions of the TT 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 NN (2≤N≤2×1052\le N\le 2\times 10^5) representing the number of vertices.

For each ii (1≤i≤N−11\le i\le N-1), the ii-th of the following N−1N-1 lines contains two integers uiu_i and viv_i (1≤ui,vi≤N1\le u_i,v_i\le N) separated by a space, representing that the ii-th edge connects vertices uiu_i and viv_i. It is guaranteed that the given graph is a tree.

The last line contains NN integers A1,A2,…,ANA_1,A_2,\ldots,A_N (Ai∈{0,1}A_i\in\{0,1\}) separated by spaces. AiA_i represents whether a stone is initially placed on vertex ii.

The sum of NN over all test cases does not exceed 2×1052\times 10^5.

Output Format

For each test case, print the answer as follows.

If it is impossible to perform the operation exactly N−1N-1 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, eke_k (1≤ek≤N−11\le e_k\le N-1) represents the index of the edge selected in the kk-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