求助站外题

就是给定一棵带权树

(节点数\leq 50000,边权<2^{20})

，

定义

f(u,v)

为从

u

到

v

的路经上边的按位与值，

g(u,v)

为从

u

到

v

的路经上边的按位或值

求

\sum^{n}_{i=1}\sum^{n}_{j=i+1}f(i,j)g(i,j) \mod 998244353

我的想法是，根据乘法分配律，

f(i,j)和g(i,j)

每一位都可单独处理,即枚举

x,y

,计算有多少对

i,j

满足

f(i,j)

的第

x

位和

g(i,j)

的第

y

位为

1

枚举了

x,y

，那么可以通过将

f(i,j)

的第

x

位为

1

的对数、和

f(i,j)

的第

x

位为

1

且

g(i,j)

的第y位为

0

的对数相减得到。对于前者，只留下第

x

位为

1

的边，然后计算连通的点对数；对于后者，只留下第

x

位为

1

且第

y

位为

0

的边，然后计算连通的点对数。

我这样做TLE了3个点，有没有人能优化一下计算点对的速度

下面是这个菜鸡的代码

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int hd[50007],nxt[100007],to[100007],w[100007],cnt,sum;
void adde(int u,int v,int wg){
	nxt[++cnt]=hd[u];
	hd[u]=cnt;
	to[cnt]=v;
	w[cnt]=wg;
}
int n,ls[50007],ls2[50007],cnt2;
void dfs1(int u,int fa,int he){
	ls[u]=cnt2;
	ls2[cnt2]++;
	for(int i=hd[u];i;i=nxt[i]){
		if(to[i]==fa)
		{
			continue;
		}
		if((w[i]&he)==0)
		{
			continue;
		}
		dfs1(to[i],u,he);
	}
}
void dfs2(int u,int fa,int he,int hou){
	ls[u]=cnt2;
	ls2[cnt2]++;
	for(int i=hd[u];i;i=nxt[i]){
		if(to[i]==fa)
		{
			continue;
		}
		if((w[i]&he)==0)
		{
			continue;
		}
		if((w[i]&hou)!=0)
		{
			continue;
		}
		dfs2(to[i],u,he,hou);
	}
}
signed main(){
	cin>>n;	
	for(int i=1;i<n;i++){
		int p1,p2,p3;
		cin>>p1>>p2>>p3;
		adde(p1,p2,p3);
		adde(p2,p1,p3);
	}
	for(int i=0;i<20;i++){
		for(int j=0;j<20;j++){
			int p1=(1<<i),p2=(1<<j);
			cnt2=0;
			for(int k=1;k<=n;k++){
				if(!ls[k])
				{
					++cnt2;
					dfs1(k,0,p1);
				}
			}
			int s1=0;
			for(int i=1;i<=cnt2;i++){
				s1=(s1+((ls2[i]*(ls2[i]-1)/2)%mod))%mod;
			}
			for(int i=1;i<=n;i++){
				ls[i]=0;
			}
			for(int i=1;i<=cnt2;i++){
				ls2[i]=0;
			}
			cnt2=0;
			for(int k=1;k<=n;k++){
				if(!ls[k])
				{
					++cnt2;
					dfs2(k,0,p1,p2);
				}
			}
			int s2=0;
			for(int i=1;i<=cnt2;i++){
				s2=(s2+((ls2[i]*(ls2[i]-1)/2)%mod))%mod;
			}
			for(int i=1;i<=n;i++){
				ls[i]=0;
			}
			for(int i=1;i<=cnt2;i++){
				ls2[i]=0;
			}
			sum=(sum+((s1-s2)*((p1*p2)%mod)%mod))%mod;
		}
	}
	cout<<sum;
	return 0;
}

讨论操作

回复

相关推荐

求助站外题