Description

从 CTSEU 毕业之后，wwlw 去 CTSEU 附属小学当了校长。为了保证同学们上学准时且安全，他决定开设校车接送同学们上学。

学校附近的城市路网可以用一个 $n$ 个路口 $n-1$ 条双向道路的连通图表示。每个路口有一个类型 $c_i$。在经过考量之后，wwlw 打算按如下方式选择两条路径作为校车运行线路。

• 一条路径两端的路口不同。
• 一条路径两端的路口类型必须相同。
• 两条路径不经过重复路口。

但由于路网更新的问题，接下来 $n$ 天，某一个路口将会施工。为了学生安全考虑，不能在施工的路口停车。具体地，今天（第 $0$ 天）没有路口施工，对于第 $i$ 天，有且仅有编号为 $i$ 的路口施工，校车可以经过此路口，但不可以将此路口作为线路两端。

现在，wwlw 想知道对于每一天，有多少种校车路线选择方案。两条校车行驶路径相同当且仅当两条路径两端的路口形成的无序对相同。两种校车路线选择方案相同当且仅当两种方案选择的路线构成的无序对相同。

Input

第一行一个整数 $n$（$2\le n\le 10^5$）。

第二行一行 $n$ 个整数 $c_1,c_2,\ldots,c_n$（$1\le c_i\le n$），表示每个路口的类型。

接下来 $n-1$ 行，每行两个整数 $x,y$（$1\le x,y\le n,x\neq y$），描述城市路网。保证给出的城市路网连通且无重边。

Output

输出 $n+1$ 行，第 $i$ 行输出第 $i-1$ 天时的答案。

Samples

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

9
3
3
3
3
3
3

Note

对于第二天，路口 $2$ 施工，但可以选择 $(3,4)$ 作为校车线路。

Resources

The 23rd UESTC Programming Contest Final