给定一棵包含 n 个节点的树，第 i 个节点具有点权值 a[i] 。
定义统一树为树上所有点权值均相等的树。
你需要计算将这棵树变成以指定节点为根的情况下的统一树。你可以进行任意次以下操作：
 - 选择一个节点 x 和一个非负整数 y ，花费 y*size[x] 的代价，将 x 为根的子树内的所有节点的点权值均异或 y ，其中 size[x] 为将 x 为根的子树内的节点数。

求根节点分别为 1,2,...,n 时将树变为统一树所需的最小代价。

第一行包含一个正整数 T (1≤T≤2·10^5) ，表示数据组数。
每组数据第一行包含一个正整数 n (1≤n≤2·10^5) ，表示树上节点数。
每组数据第二行包含 n 个正整数 a[1],a[2],...,a[n] (1≤a[i]<2^20) ，表示每个节点的点权值。
每组数据接下来 n-1 行，每行包含两个整数 u,v (1≤u,v<n) ，表示节点 u 和节点 v 之间有一条连边。

保证输入的边构成一棵树。
保证所有 n 之和不超过 2·10^5 。

输出 n 个整数，分别表示根节点为 1,2,...,n 时将树变为统一树所需的最小代价。

2
4
3 2 1 0
1 2
2 3
2 4
1
100

8 6 12 10 
0

样例解释
在第一组数据中，当根节点为 1 时，可以进行如下操作：
1. 选择 x=2 和 y=1 ， a 将变成 [3,3,0,1] ，花费代价 3 。
2. 选择 x=3 和 y=3 ， a 将变成 [3,3,3,1] ，花费代价 3 。
3. 选择 x=4 和 y=2 ， a 将变成 [3,3,3,3] ，花费代价 2 。
总花费 3+3+2=8 。

当根节点为 2,3,4 时，以此类推。

在第二组数据中，目标已经实现，因为只有一个顶点。