AT_abc201_e [ABC201E] Xor Distances 题解

题目大意：

给定一颗带边权无根树，定义

dis(i,j)

表示

i,j

两点在树上的最短路径中所有边权异或的值。求：

\sum_{i = 1}^{n} \sum_{j = i+1}^{n} dis(i,j)

思路：

首先明确一点，即：

dis(i,j)=dis(root,i) \oplus dis(root,j)

因为两者的公共部分由于异或而抵消了。

那我们可以先预处理出来根节点到每一个节点的权值，即

dis(i,j)

。接着我们按位考虑，假设第

k

位的某一段有贡献，那只可能是

1

，那要得到这个贡献必须是

0 \oplus 1

。我们要求所有有贡献的段，考虑如何计算，先统计

1

的个数设为

cnt

，

cnt=\sum_{i=1}^{n} (dis(root,i) \gg k) \& 1

，则

0

的个数为

n-cnt

那可以产生贡献的段的贡献和即为

cnt \times (n-cnt)

，别忘了我们每次只枚举第

k

位，所以最终：

ans+= \sum_{k=0}^{60} 2 ^{k} \times cnt \times (n-cnt)

即为所求。另注意取模。

代码：

CPP

#include<bits/stdc++.h>
#define int long long
#define Up(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
const int N=2e5+10,mod=1e9+7;
int n,ans;
struct Edge{
	int v,w;
};
vector<Edge> e[N];
int d[N];
void dfs(int u,int fa){
	for(auto it:e[u]){
		if(it.v==fa) continue;
		d[it.v]=d[u]^it.w;
		dfs(it.v,u);
	}
}
signed main(){
	cin.tie(0),cout.tie(0)->sync_with_stdio(0);
	cin>>n;
	Up(i,1,n-1){
		int u,v,w;
		cin>>u>>v>>w;
		e[u].push_back({v,w});
		e[v].push_back({u,w});
	}
	d[1]=0;
	dfs(1,0);
	Up(k,0,60){
		int cnt=0;
		Up(i,1,n) cnt+=((d[i]>>k)&1ll);
		cnt%=mod;
		ans+=((1ll<<k)%mod)*(cnt*(n-cnt)%mod)%mod;
		ans%=mod;
	}
	cout<<ans<<"\n";
	return 0;
}

AT_abc201_e [ABC201E] Xor Distances 题解

文章操作

题目大意：

思路：

代码：

相关推荐

评论

AT_abc201_e [ABC201E] Xor Distances 题解