解题思路

设节点 $u$ 的子树为 $T_u$，题目要求的是：

直接枚举子树内所有点对显然不行，因为点对数量太多。

题目内容

$Bingbong$ 给定一棵包含$n$个节点的树，节点编号为 $1$∼$n$，根节点为编号$1$的节点。每个节点$u$有一个权值 $a_u$。

他想针对每个节点 $u$，在以 $u$ 为根的子树内统计节点权值之间的异或总和。

具体来说，对于每个节点 $u (1≤u≤n)$，计算以 u 为根的子树内所有不同节点对$(x,y) (x<y)$的权值异或之和：

$∑_{x,y∈T_u}, x<y(a_x⊕a_y)$

其中 $T_u$ 表示以$u$为根的子树节点集合。

名词解释

• 按位异或 (⊕)：二进制逐位运算，相同为 $0$、不同为 $1$。例如$5⊕3=6$。
• 子树：对于树中某个节点，其与所有后代节点构成的集合称为该节点的子树。

输入描述

第一行：一个整数 $n (1≤n≤2×10^5)$，表示节点总数。

第二行：$n$个整数，依次为 $a_1,a_2,…,a_n (1≤a_i≤10^6)$，表示各节点权值。

接下来 $n−1$ 行：每行两个整数$u,v (1≤u,v≤n,u≠v)$，表示节点 $u$与节点$v$之间存在一条无向边。

给定的边构成一棵以节点 $1$为根的树，用于定义父子关系与子树

输出描述

输出$n$个整数。第$u$个整数为以节点$u$为根的子树内所有节点对权值异或之和。各数之间可以用空格分隔。

样例1

输入

3
1 2 3
1 2 
1 3

输出

6 0 0

样例2

输入

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

输出

42 14 0 0 0