题目描述

“连团战都不会，真菜。”

收到队友这样的评论后，新手小 C 破防了。他打算尝试一款新的多人游戏。游戏有 $n$ 人参加，围坐成一个环，每人初始有 $1$ 张牌。从任意一个人开始进行第一轮操作。对于游戏的第 $i$ 轮，假设操作的人为 $x$，$x$ 顺时针方向的下一个人为 $y$，操作过程为：

1. $x$ 需要给 $y$ 共 $2-i\bmod 2$ 张牌，如果超过了自身手牌数，则将手上的牌全部给出。
2. 如果 $x$ 此时没牌了，$x$ 从环内退出；如果此时环上只剩下一个人，则游戏结束。
3. 如果游戏没有结束，第 $i+1$ 轮操作的人为 $y$。

在有些参加人数 $n$ 的状况下，游戏会出现循环。新手小 C 定义了一个函数 $f(n)$，表示 $n$ 个人玩这个游戏时，最终游戏进入循环时，最短循环节包含的轮次数是多少。

具体来说，一次游戏当中，两个状态相同当且仅当两个状态中环上人数相同，每人手中的牌数相同，且下一次该操作的人相同。$f(n)$ 表示 $n$ 个人开始游戏，不断进行下去，状态相同的两个轮次的轮次编号差值的最小值。特别地，如果 $n$ 个人开始游戏，游戏最终结束，则 $f(n)=0$。

新手小 C 还在玩这个简单的游戏的时候，你已经开始研究数数了。现在你拿到了一棵 $m$ 个点的树，每个点有点权 $v_i$，边长均为 $1$。设树上两点 $x,y$ 的最短距离为 $\operatorname{dis}(x,y)$。你现在想知道对于每个点 $x$，

$\sum_j f\!\left(v_j+\operatorname{dis}(x,j)\right)$

的值是多少呢？

输入格式

第一行一个整数 $m$，表示树的节点个数。

接下来一行 $m$ 个整数，依次表示 $v_i$。

接下来 $m-1$ 行，每行两个整数 $x,y$，表示树上一条连接 $x,y$ 的无向边，保证给出的图是一棵树。

输出格式

一行 $m$ 个整数，表示对于每个点的答案。

样例输入

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

样例输出

12 12 0 0 0

样例解释

对于 $1$ 号点，各节点距离为 $0,1,2,4,3$，所求答案为

$f(1)+f(3)+f(5)+f(8)+f(8)$。

$n=1,3,5$ 时游戏会结束，$n=8$ 时最终循环的六个状态为：

$4,2,2;\ 3,3,2;\ 3,1,4;\ 4,1,3;\ 2,3,3;\ 2,2,4$，

$f(8)=6$。因此 $1$ 号点答案为 $12$。其余点的计算方式类似。

数据范围

对于全部的数据：

• $1\le m\le10^5$
• $1\le v_i\le m$
• $1\le x,y\le m$
• 保证所有输入的边构成一棵树