就是给定一棵带权树$(节点数\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个点，有没有人能优化一下计算点对的速度

下面是这个菜鸡的代码

#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;
}