C++(clang++11) 解法, 执行用时: 682ms, 内存消耗: 33204K, 提交时间: 2021-04-16 19:16:56

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
int p1=5000000;
char buf[5000005];
int gc(){
	if(p1>=5000000)fread(buf,1,5000000,stdin),p1=0;
	return buf[p1++];
}
int rd(){
	int x=0,ch=gc();
	while(!isdigit(ch))ch=gc();
	while(isdigit(ch))x=x*10+ch-'0',ch=gc();
	return x;
}
int n,m,dfn[200005],low[200005],st[200005],fa[200005],loop[200005],top,sign,cnt=0,w[200005];
ll ans=0;
int s[200005][22],size[200005];
vector<int> g[200005];
int gf(int x){
	return fa[x]==x?x:fa[x]=gf(fa[x]);
}
struct E{
	int x,y,val;
}e[200005];
unordered_map<ll,int> mp;
void dfs(int x,int fr){
	dfn[x]=low[x]=++sign,st[++top]=x;
	for(int y:g[x]){
		if(!dfn[y]){
			dfs(y,x),low[x]=min(low[x],low[y]);
			if(low[y]>=dfn[x]){
				loop[0]=0;
				do {
					loop[++loop[0]]=st[top--];
				} while(loop[loop[0]]!=y);
				loop[++loop[0]]=x;
				if(low[y]!=dfn[y]){
					int mn=1e9,mnp=0;
					for(int i=1;i<=loop[0];i++){
						w[i]=mp[200000ll*loop[i]+loop[i%loop[0]+1]];
						if(w[i]<mn)mn=w[i],mnp=i;
					}
					for(int i=1;i<=loop[0];i++)if(i^mnp)e[++cnt]={loop[i],loop[i%loop[0]+1],mn+w[i]};
				}
				else e[++cnt]={x,y,mp[200000ll*x+y]};
			}
		}
		else if(y!=fr)low[x]=min(low[x],dfn[y]);
	}
}
void Solve(){
	n=rd(),m=rd(),cnt=top=sign=ans=0,mp.clear();
	for(int i=1;i<=n;i++)g[i].clear(),dfn[i]=low[i]=0;
	for(int i=1,x,y,z;i<=m;i++)x=rd(),y=rd(),z=rd(),g[x].push_back(y),g[y].push_back(x),mp[200000ll*x+y]=mp[200000ll*y+x]=z;
	dfs(1,0),sort(e+1,e+cnt+1,[](E x,E y){return x.val>y.val;});
	for(int i=1;i<=n;i++){
		fa[i]=i,size[i]=1;
		for(int j=0;j<21;j++)s[i][j]=((i>>j)&1);
	}
	for(int i=1;i<=cnt;i++){
		int x=gf(e[i].x),y=gf(e[i].y),w=e[i].val;
		for(int j=0;j<21;j++){
			if((w>>j)&1)ans+=(1ll<<j)*(1ll*s[x][j]*s[y][j]+1ll*(size[x]-s[x][j])*(size[y]-s[y][j]));
			else ans+=(1ll<<j)*(1ll*s[x][j]*(size[y]-s[y][j])+1ll*s[y][j]*(size[x]-s[x][j]));
		}
		fa[y]=x,size[x]+=size[y];
		for(int j=0;j<21;j++)s[x][j]+=s[y][j];
	}
	cout<<ans<<'\n';
}
int main(){
	int t=rd();
	while(t--)Solve();
}