题目内容

在一个星际联盟中，有 $n$ 个星球，它们通过 $n-1$ 条星际航道连接成一棵以星球 $1$ 为根的层级管理树。每个星球 $u$ 有一个能量值 $e_u$。

对于某个星球 $u$，定义其管辖区域 $S_u$ 为以星球 $u$ 为根的子树中所有星球的集合（包含星球 $u$ 自身）。在该区域内，任意两个不同星球 $x$ 与 $y$ 的组合会产生一个能量差异度，其值为 $e_x \oplus e_y$，其中 $\oplus$ 表示按位异或运算（二进制位相同为 $0$，不同为 $1$）。

星球 $u$ 的管辖混乱度定义为管辖区域 $S_u$ 中所有无序星球对 $(x, y)$（满足 $x < y$）的能量差异度之和：

请你计算并输出每个星球的管辖混乱度。

星球数量 $n$ 不超过 $2 \times 10^5$，能量值 $e_i$ 均为不超过 $10^6$ 的正整数。

输入描述

第一行包含一个整数 $n$，表示星球的数量。 第二行包含 $n$ 个整数 $e_1, e_2, \dots, e_n$，依次表示编号 $1$ 到 $n$ 的星球的能量值。 接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示星球 $u$ 与星球 $v$ 之间有一条直接星际航道。输入保证这些航道构成一棵以星球 $1$ 为根的树，并且不形成环。

输出描述

输出一行共 $n$ 个整数，第 $i$ 个整数表示以星球 $i$ 为根的管辖区域的混乱度，整数之间用单个空格分隔。

样例1

输入

1
5

输出

0

说明

星球数量为 1，管辖区域只包含星球自身，区域内不存在其他星球可以组成无序对，因此管辖混乱度为 0。

样例2

输入

2
1 2
1 2

输出

3 0

说明

树以星球 1 为根，星球 1 管辖区域为 $\{1, 2\}$，仅有一对星球 $(1,2)$，能量差异度为 $e_1 \oplus e_2 = 1 \oplus 2 = 3$，混乱度为 3。 星球 2 管辖区域仅包含自己，不存在点对，混乱度为 0。

样例3

输入

3
1 2 3
1 2
2 3

输出

6 1 0

说明

树结构为一条链 1-2-3，以 1 为根。 星球 1 的管辖区域为 $\{1,2,3\}$，共有 $3$ 对无序点对：$(1,2)$ 异或值为 $1 \oplus 2 = 3$，$(1,3)$ 异或值为 $1 \oplus 3 = 2$，$(2,3)$ 异或值为 $2 \oplus 3 = 1$，总和为 $3+2+1=6$。 星球 2 的管辖区域为 $\{2,3\}$，仅有一对 $(2,3)$，异或值为 $2 \oplus 3 = 1$，混乱度为 1。 星球 3 管辖区域仅包含自身，混乱度为 0。

样例4

输入

4
1 2 3 4
1 2
1 3
2 4

输出

24 6 0 0

说明

树结构：星球 1 连接 2 和 3，星球 2 连接 4。 星球 1 的管辖区域为整棵树 $\{1,2,3,4\}$，共 $\binom{4}{2}=6$ 个点对。各点对异或值：$1 \oplus 2 = 3$，$1 \oplus 3 = 2$，$1 \oplus 4 = 5$，$2 \oplus 3 = 1$，$2 \oplus 4 = 6$，$3 \oplus 4 = 7$，总和为 $3+2+5+1+6+7=24$。 星球 2 的管辖区域为 $\{2,4\}$，点对 $(2,4)$ 异或值为 $2 \oplus 4 = 6$，混乱度为 6。 星球 3 和星球 4 的管辖区域均只包含自身，混乱度为 0。