For a tree (T) with root (r), where each node (u) has a value (a_u) associated with it, the cost of the tree defined as: ()\sum_{u\in T} (a_u \cdot d(r,u))() Here, this sum is taken over all nodes (u) in the tree (T), and (d(r,u)) denotes the number of edges on the shortest path from node (r) to node (u) on a tree. You are given a tree consisting of (n) nodes, rooted at node (1). Each node (i) has a value (a_i) assigned to it. For each (r) from (1) to (n), please solve the following problem independently: Consider the subtree of node (r) with respect to node (1). Formally, the subtree of node (r) is the tree consisting of all nodes (u) such that the shortest path from (1) to (u) contains (r). Find the maximum cost of the subtree after performing at most one operation of the following type on the subtree: Choose any node (u) ((u \neq r)). Remove the edge from (u) to the parent of node (u)(^{\text{∗}}). Then, add an edge from (u) to any node (v) that is still reachable from (r). It can be shown that after this operation, the graph remains a tree. (^{\text{∗}})Formally, remove the edge from (u) to (p), where (p) is the unique node satisfying (d(u,p)=1) and (d(u,r)=d(p,r)+1) Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 10^4)). The description of the test cases follows. The first line of each testcase contains a single integer (n) ((1 \le n \le 2 \cdot 10^5)) — the count of nodes in the tree. The second line of each testcase contains (n) integers (a_1, a_2, \ldots, a_n) ((1 \le a_i \le 2 \cdot 10^5)). Then (n − 1) lines follow, the (i)-th line containing two integers (u) and (v) ((1 \le u, v \le n)) — the two nodes that the (i)-th edge connects. It is guaranteed that the given edges form a tree.