C++(g++ 7.5.0) 解法, 执行用时: 519ms, 内存消耗: 14532K, 提交时间: 2022-10-19 17:41:31

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int N=1000005,mod=998244353;
int k,n,m,siz[N],fa[N];
ll tot,ans;
ll power(ll x,ll y){
	ll res=1;
	while(y){
		if(y%2)	res=(res*x)%mod;
		x=(x*x)%mod;
		y>>=1;
	}
	return res;
}
int get(int x){
	if(x==fa[x])	return x;
	return fa[x]=get(fa[x]);
}
struct xx{
	int x,y,z,id;
}w[N];
bool cmp(xx p,xx q){
	return p.z<q.z;
}
void kruskal(){
	for(int i=1;i<=m;i++){
		int p=get(w[i].x);
		int q=get(w[i].y);
		int v=w[i].z;
		int id=w[i].id;
		if(p==q)	continue;
		fa[p]=q;
//		cout<<v<<endl;
		ans=(ans+(v*tot%mod)*power(siz[id],mod-2)%mod)%mod;
		tot=((tot*power(siz[id],mod-2)%mod)*(siz[id]-1))%mod;
		siz[id]--;
	}
}
int main(){
	cin>>k;
	tot=1;
	for(int i=1;i<=k;i++){
		int _n,_m;
		scanf("%d%d",&_n,&_m);
		for(int j=1;j<=_m;j++){
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			a+=n;
			b+=n;
			w[++m]={a,b,c,i};
		}
		n+=_n;
		siz[i]=_n;
		tot=(tot*_n)%mod;
	}
	for(int i=1;i<=n;i++)	fa[i]=i;
	sort(w+1,w+m+1,cmp);
	kruskal();
	cout<<ans;
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 398ms, 内存消耗: 18436K, 提交时间: 2023-07-23 20:51:18

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7,p=998244353;
int n,m,q,s,k,w[N],f[N],inv[N];
struct edge{
	int a,b,c,d;
}e[N];
inline int g(int u){
	if(f[u]==u) return u; return f[u]=g(f[u]);
}
inline bool cmp(edge A,edge B){
	return A.c<B.c;
}
int main(){
	inv[1]=1;
    for(int i=2;i<=1000000;i++) inv[i]=1ll*(p-p/i)*inv[p%i]%p;
	cin>>k; long long S=1;
	for(int i=1;i<=k;i++){
		scanf("%d%d",&n,&q),w[i]=n,S=S*w[i]%p;
		while(q--){
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z),x+=s,y+=s;
			m++,e[m].a=x,e[m].b=y,e[m].c=z,e[m].d=i;
		}
		s+=n;
	}
	for(int i=1;i<=s;i++) f[i]=i;
	sort(e+1,e+m+1,cmp); int ans=0;
	for(int i=1;i<=m;i++){
		if(g(e[i].a)==g(e[i].b)) continue;
		f[g(e[i].a)]=g(e[i].b);
		ans=(ans+1ll*inv[w[e[i].d]]*S%p*e[i].c)%p;
		S=1ll*S*inv[w[e[i].d]]%p*(w[e[i].d]-1)%p;
		w[e[i].d]--;
	}
	cout<<ans<<endl;
	return 0;
}