405168: GYM101808 H Shahhoud the Chief Judge

Shahhoud is the Chief Judge for SCPC 2019. He created an interesting problem:

Given a binary tree with N nodes where each node has a weight assigned to it, your task is to find the sum of all paths in the tree (including the path from a node to itself). In other words, you need to calculate the sum of D(u, v) for every 1 ≤ u, v ≤ N. D(u, v) is the sum of the weights of the nodes on the path from u to v.

Shahhoud generated test cases for the problem, but then he realized that he doesn't know how to solve it. In order to create test cases for the problem, judges usually need a correct solution to generate the correct output for each test case.

In order to solve this problem, he decided to edit the test cases such that the answer is always 0. This way, he doesn't need a correct solution because the output is always the same!

Manually editing the test cases is time consuming, so he asked you for help. He needs to know the minimum number of nodes that he must change their weights such that the answer becomes 0. He also needs the nodes that should be changed.

The weights of the chosen nodes can be changed to any integer number .

If there is more than one optimal solution, output any.

The first line contains a single integer T, the number of test cases Shahhoud generated.

Each test case starts with a line containing a single integer N, the number of nodes in the binary tree. (1 ≤ N ≤ 10⁵).

The following line contains N space-separated integers w_i, the weight of the i^th node. ( - 1000 ≤ w_i ≤ 1000).

N - 1 lines follow, each containing two space-separated integers u_i and v_i. This means that there is an edge between nodes u_i and v_i. (1 ≤ u_i, v_i ≤ N)

For each test case, print one line that starts with K, the minimum number of nodes that need to be changed so that the answer becomes 0, followed by a space, then K space-separated integers v_i, the nodes that need to be changed.

1
3
0 1 -1
1 2
1 3

0

A binary tree is a tree where every node is either a leaf, or has two sons.