czq获得了以1号节点为根的一颗五彩缤纷的树，树的每个节点都有一种颜色cic_ici。
czq对每颗子树都定义了一个“缤纷值”，如果子树中颜色为jjj的节点有aja_jaj个，那么将对“缤纷值”产生aj3a_j^3aj3的贡献。czq想知道这颗树以每个节点为根的子树的缤纷值。
第一行一个整数nnn。
接下来一行有nnn个整数cic_ici，为每个节点的颜色。
接下来n−1n-1n−1行，每行两个整数ui,viu_i,v_iui,vi，为树的边。
输出仅一行nnn个整数，为每个节点的“缤纷值”。
6 1 1 4 5 1 4 1 2 2 3 2 4 3 5 3 6
36 17 9 1 1 1
1≤n≤1051 \leq n \leq 10^51≤n≤105
1≤ci,ui,vi≤n1 \leq c_i,u_i,v_i \leq n1≤ci,ui,vi≤n