Subtree Value Range

Given a tree with (N) nodes where each node has an associated integer value, you are required to compute, for every node, the difference between the maximum and minimum values found in its subtree. Here, the subtree of a node consists of the node itself and all its descendants (when the tree is rooted at node 1). Formally, for each node (i), define its answer as [ diff(i)=\max{ a_j : j \in subtree(i) } - \min{ a_j : j \in subtree(i) }. ]

You are given multiple test cases. For each test case, the first input is the number of nodes (N). The next line contains (N) integers representing the node values. This is followed by (N-1) lines, each containing two integers (u) and (v), which indicate an undirected edge between node (u) and node (v). It is guaranteed that the given graph forms a tree. The tree is considered rooted at node 1.

inputFormat

The input begins with an integer (T) denoting the number of test cases. For each test case:

1. A line containing an integer (N) (the number of nodes in the tree).
2. A line with (N) space-separated integers representing the values of the nodes (in order from 1 to (N)).
3. (N-1) lines, each containing two integers (u) and (v) denoting an undirected edge between nodes (u) and (v).

All input should be read from standard input (stdin).

outputFormat

For each test case, output a single line with (N) space-separated integers. The (i)th integer is the difference between the maximum and minimum values in the subtree of node (i). The output should be written to standard output (stdout).## sample

1
5
1 3 7 4 6
1 2
1 3
3 4
3 5

6 0 3 0 0