405476: GYM101972 B Updating the Tree

A rooted tree is a tree with a countable number of nodes, in which a particular node is distinguished from the others by being the ancestor node of every node of the tree. This node is called the root node.

You are given a rooted tree consisting of n nodes numbered from 1 to n. The root of the tree is node number 1. Each node i has a value v_i assigned to it.

For each subtree, you must find the minimum number of nodes you must change the value on them to any other value so that the distance between every pair of nodes in that subtree is equal to the absolute difference between the values on them, or say that it is impossible. Can you?

The first line contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.

The first line of each test case contains an integer n (1 ≤ n ≤ 10⁵), in which n is the number of nodes in the tree. Then a line follow containing n integers v₁, ..., v_n (1 ≤ v_i ≤ 10⁵), in which v_i is the value of the i^th node.

Then n - 1 lines follow, each line contains two integers a_i and b_i (1 ≤ a_i, b_i ≤ n), giving an edge between nodes a_i and b_i.

For each test case, print a single line containing n space-separated integers x₁, ..., x_n, in which x_i is the answer of the subtree of node i. If an answer does not exist for a subtree, print  - 1.

1
2
1 3
1 2

1 0