设节点 u 的子树为 Tu,题目要求的是:
x,y∈Tu, x<y∑(ax⊕ay)直接枚举子树内所有点对显然不行,因为点对数量太多。
Bingbong 给定一棵包含n个节点的树,节点编号为 1∼n,根节点为编号1的节点。每个节点u有一个权值 au。
他想针对每个节点 u,在以 u 为根的子树内统计节点权值之间的异或总和。
具体来说,对于每个节点 u(1≤u≤n),计算以 u 为根的子树内所有不同节点对(x,y)(x<y)的权值异或之和:
∑x,y∈Tu,x<y(ax⊕ay)
其中 Tu 表示以u为根的子树节点集合。
名词解释
第一行:一个整数 n(1≤n≤2×105),表示节点总数。
第二行:n个整数,依次为 a1,a2,…,an(1≤ai≤106),表示各节点权值。
接下来 n−1 行:每行两个整数u,v(1≤u,v≤n,u=v),表示节点 u与节点v之间存在一条无向边。
给定的边构成一棵以节点 1为根的树,用于定义父子关系与子树
输出n个整数。第u个整数为以节点u为根的子树内所有节点对权值异或之和。各数之间可以用空格分隔。
输入
3
1 2 3
1 2
1 3
输出
6 0 0
输入
5
1 2 3 4 5
1 2
1 3
2 4
2 5
输出
42 14 0 0 0