Tree Danger Value Computation

Given a tree \(T\) with \(n\) nodes numbered from \(1\) to \(n\) and rooted at node \(1\), where each node \(i\) has an associated weight \(w_i\) representing its danger level, you are asked to compute a danger value for each subtree \(T_u\) of \(T\). Here, \(T_u\) is the subtree obtained by removing the edge between \(u\) and its parent (with the convention that \(T_1=T\)).

We define the following:

• Lowest Common Ancestor (LCA): In a rooted tree with root \(r\), the lowest common ancestor of two nodes \(u\) and \(v\) is defined as the common ancestor that is farthest from the root, denoted by \(\operatorname{lca}(r,u,v)\). For three nodes \(i, j, k\), we define their common ancestor as \(\operatorname{lca}(i,j,k)=\operatorname{lca}(\operatorname{lca}(i,j),k)\).
• Subtree \(T_u\): For a node \(u\) in \(T\), after removing the edge connecting \(u\) with its parent, the connected component containing \(u\) is denoted as the subtree \(T_u\). (Note that \(T_1\) is the whole tree.)
• Danger Value: For a given subtree \(T_u\), its danger value is defined as \[ \mathrm{LCAS}(u)=\sum_{i\in T_u}\;\sum_{j\in T_u}\;\sum_{\substack{k\in T_u\\ k<j}} w_{\operatorname{lca}(i,j,k)}. \] In other words, for every ordered triple \((i,j,k)\) with \(i,j,k\in T_u\) and with \(k<j\) (by their node numbers), compute \(w_{\ell}\) where \(\ell\) is the lowest common ancestor of \(i, j, k\) (computed as \(\operatorname{lca}(\operatorname{lca}(i,j),k)\) with respect to the original tree rooted at \(1\)), and sum these values up.

Your task is to compute \(\mathrm{LCAS}(u)\) for each \(u=1,2,\dots,n\).

inputFormat

The first line contains an integer \(n\) \( (1 \leq n \leq 50)\), the number of nodes in the tree. The second line contains \(n\) integers \(w_1, w_2, \dots, w_n\) denoting the weight of each node. Each of the following \(n-1\) lines contains two integers \(u\) and \(v\), representing an undirected edge connecting nodes \(u\) and \(v\). It is guaranteed that the edges form a tree and that the tree is rooted at node \(1\).

outputFormat

Output \(n\) space‐separated integers where the \(i\)th integer is \(\mathrm{LCAS}(i)\), the danger value for the subtree rooted at node \(i\).

sample

3
1 2 3
1 2
1 3

9 0 0