自动搬运

查看原文

来自洛谷，原作者为

	dayz_break404 我与旧事归于尽，来年依旧迎花开

搬运于2025-08-24 22:28:40，当前版本为作者最后更新于2024-10-07 15:30:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

注意到位运算每一位都是独立的，考虑将权值的每一位拆开，单独考虑每一位对答案的贡献。

先枚举每一位，这样原树就变成了一颗只有 $0$ 和 $1$ 的树。很明显只有当路径上的 $1$ 的个数为奇数时，这条路径才会对答案产生贡献。

记 $dp_{u,0}$ 表示路径的一个端点为 $u$，另一个端点在 $u$ 的子树，路径上的 $1$ 的个数为偶数时，这样的路径的条数。同理 $dp_{u,1}$ 为 $1$ 的个数为奇数。

转移时进行分类讨论：

• 若当前的节点 $u$ 第 $w$ 位是 $1$，那么对于其每一个子节点 $v$，有 $dp_{u,0}+=dp_{v,1},dp_{u,1}+=dp_{v,0}$。
• 若当前的节点 $u$ 第 $w$ 位是 $0$，那么对于其每一个子节点 $v$，有 $dp_{u,0}+=dp_{v,0},dp_{u,1}+=dp_{v,1}$。

考虑如何计算答案，显然对于一条路径只有两种情况：

• $lca_{a,b}$ 不为 $a$ 或者 $b$，有 $ans+=dp_{u,1}\times dp_{v,0}+dp_{u,0}\times dp_{v,1}$，其中 $v$ 是 $u$ 的子节点。
• $lca_{a,b}$ 为 $a$ 或者 $b$ 其中一个，有 $ans+=dp_{u,1}$。

时间复杂度 $O(n\log V)$，其中 $V$ 为值域。

代码：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*f;
}
#define ll long long
const int maxn=1e5+20;
int a[maxn],n,head[maxn],idx,dp[maxn][2],mul[40];
ll ans;
struct node{
	int nxt,to;
}e[maxn<<1];
inline void add(int u,int v){
	e[++idx].to=v,e[idx].nxt=head[u],head[u]=idx;
}
void dfs(int u,int fa,int w){
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa) continue;
		dfs(v,u,w);
		ans+=1ll*dp[u][1]*dp[v][0]*mul[w]+1ll*dp[u][0]*dp[v][1]*mul[w];
		if(a[u]&1) dp[u][0]+=dp[v][1],dp[u][1]+=dp[v][0];
		else dp[u][0]+=dp[v][0],dp[u][1]+=dp[v][1];
	}
	dp[u][a[u]&1]++;
	ans+=1ll*dp[u][1]*mul[w];
}
int main(){
	mul[0]=1;
	for(int i=1;i<=30;i++) mul[i]=mul[i-1]*2;
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	int u,v;
	for(int i=1;i<n;i++) u=read(),v=read(),add(u,v),add(v,u);
	for(int i=0;i<=30;i++){
		dfs(1,0,i);
		for(int j=1;j<=n;j++) a[j]>>=1,dp[j][0]=dp[j][1]=0;
	}
	printf("%lld\n",ans);
	return 0;
}