Description

A 君住在魔法森林里，魔法森林可以看做一颗 $n$ 个接点的树，接点从 $1\sim n$ 编号。树中的每个接点上都生长着蘑菇。蘑菇有许多不同的种类，但同一个接点上的蘑菇都是同一个种类，更具体地，$i$号结点上生长着种种类 $c_i$ 的蘑菇。

现在 A 君打算出去采蘑菇，但他并不知道哪里的蘑菇更好，因此他选定起点 $s$ 后会等概率随机选择树中的某个节点t作为终点，之后从 $s$ 沿着 $(s，t)$ 间的最短路径走到 $t$。并且 A 君会采摘途中所经过的所有结点上的蘑菇。

现在 A 君想知道，对于每一个节点 $u$，假如他从这个节点出发，他最后能采摘到的蘑菇种类数的期望是多少。为了方便，你告诉 A 君答案 $\times n$ 的值即可。

Input Format

第一行一个整数 $n$ 表示结点数。

第二行 $n$ 个整数 $c_i$ 表示每个节点的蘑菇的种类。

接下来 $n - 1$ 行每行两个数 $u_i$， $v_i$ 表示树中的一条边。

Output Format

输出 $n$ 行每行一个整数，第 $i$ 行的整数表示起点为结点 $i$ 时的答案。

Sample

样例输入

5 
1 2 3 2 3
1 2
1 3
2 4
2 5

样例输出

10
9
12
9
11

Hint

$30\%$ 的数据： $n \leq 2000$

另有 $20\%$ 的数据：给出的第$i$条边为$\{i,i + 1\}$

另有 $20\%$ 的数据：蘑菇的种类最多 $3$ 种

$100\%$ 的数据：$1 \leq n \leq 3 \times 10^5$, $0 \leq c_i \leq n$