题意

非常简洁，给你一个有根树。求问 。

分析

我们发现 出现的非常突兀。考虑直接枚举 ，由于每个点对只计算一次。所以只用计算后加入的对前者的贡献。那么一个点的贡献为， 其它子树中权值为 的编号。但是答案为 。这个没有什么结合率和交换率。我们考虑直接拆位。那么令 表示，权值为 ，第 为 的个数。那么一个点的贡献为 。那么现在就是如果统计树上的点对。要么点分治要么树上启发式合并。时间复杂度都是 的。这里不详细展开了。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
} 
const int N = 1e6 + 52100,M = 1e5 + 100;
struct Edge {int to,nxt;}e[M << 1];
int f[N][18][2];
int head[M],ecnt;
int son[M],si[M],fa[M],L[M],id[M],R[M],Id,n,val[M];
void add(int x,int y) {e[++ecnt] = (Edge){y,head[x]};head[x] = ecnt;}
void dfs(int x,int F) {
    fa[x] = F;id[L[x] = ++Id] = x;si[x] = 1;
    for(int i = head[x];i;i = e[i].nxt) {
        int y = e[i].to;if(y == F) continue;
        dfs(y,x);si[x] += si[y];
        if(si[y] > si[son[x]]) son[x] = y;
    }R[x] = Id;
}
ll Ans = 0,Lca;
void addp(int x) {
    for(int i = 0;i < 18;i++) 
    Ans += f[val[Lca] ^ val[x]][i][!((x >> i) & 1)] * (1 << i);
}
void addt(int x) {for(int i = L[x];i <= R[x];i++) addp(id[i]);}
void inc(int x,int d) {for(int i = 0;i < 18;i++) f[val[x]][i][(x >> i) & 1]+=d;}
void solve(int x,int keep) {
    for(int i = head[x];i;i = e[i].nxt) {
        int y = e[i].to;
        if(y == fa[x] || y == son[x]) continue;
        solve(y,0);
    }
    if(son[x]) solve(son[x],1);
    Lca = x;
    for(int i = head[x];i;i = e[i].nxt) {
        int y = e[i].to;
        if(y == fa[x] || y == son[x]) continue;
        addt(y);for(int j = L[y];j <= R[y];j++) inc(id[j],1);
    }
    addp(x);inc(x,1);
    if(keep) return;
    for(int i = L[x];i <= R[x];i++) inc(id[i],-1);
}
int main() {
    n = read();
    for(int i = 1;i <= n;i++) val[i] = read();
    for(int i = 1,a,b;i < n;i++) {
        a = read();b = read();
        add(a,b);add(b,a);    
    }
    dfs(1,0);solve(1,0);
    cout << Ans << endl;
    return 0;
}