526互联

AtCoder Beginner Contest 201 E - Xor Distances

发布时间 2023-09-01 23:02:07作者: 无上大宗师

E - Xor Distances


原题链接


题意：设dist(i,j)即i到j之间路径的异或和，求树上所有两点之间dist（i，j)的和


思路：dist(i,j) = dist(i,1)^dist(j,1) 根据异或性质相同的部分会被消掉
用bfs求得dist(i,1)
优化两层i，j的枚举：通过遍历每个数的每一位1的个数cnt,以及0的个数n-cnt，从而在1^0=1得到新1的个数


#include <bits/stdc++.h>
using namespace std;
const int N = 200010,M=4*N,mod=1e9+7;
typedef long long ll;
ll d[N];//dist(1->i)的异或和 
ll e[M],h[N],ne[M],idx,w[M];
//dist(i,j)为i到j路径上的边的异或和,求所有dist(i,j)的和
void add(ll a,ll b,ll c)
{
	e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void bfs()//更快一点
{
	memset(d,-1,sizeof(d));
	queue<int> q;
	q.push(1);
    d[1]=0;
    while(q.size())
    {
		auto u=q.front();
		q.pop();
		
		for(int i=h[u];~i;i=ne[i])
		{
			int j=e[i];
			if(d[j]==-1)
			{
				d[j]=d[u]^w[i];
				q.push(j);
			}
		}
	}
}
int main()
{
	int n;
	cin>>n;
	memset(h,-1,sizeof(h));
	memset(d,-1,sizeof(d));
	for(int i=1;i<n;i++)
	{
		ll u,v;
		ll w;
		cin>>u>>v>>w;
		add(u,v,w),add(v,u,w);
	}
	
	bfs();
	//dist(i,j)=dist(i,1)^dist(j,1)
	
	ll ans=0ll;
	for(int i=0;i<60;i++)//!遍历每一位!
	{
		int cnt=0;
		for(int j=1;j<=n;j++)
		{
			if(d[j]>>i&1ll)
			{
				cnt++;
			}
		}
		ans=(ans%mod+(1ll<<i)%mod*cnt%mod*(n-cnt)%mod+mod)%mod;//ans+=(1<<i)*cnt*(n-cnt)
	}
	cout<<ans<<'\n';
}