一直以为这题要martix-tree，实际上因为有相同权值的边不大于10条于是dfs就好了...
先用kruskal求出每种权值的边要选的次数num，然后对于每种权值的边2^num暴搜一下选择的情况算出多少种情况合法，对于每种权值的边的方案用乘法原理乘起来就是答案了
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int maxn=500010,mod=31011; struct poi{int x,y,z,pos;}a[maxn]; int n,m,cntt,sum,cnt,ans; int num[maxn],fa[maxn],l[maxn],r[maxn]; inline void read(int &k) { int f=1;k=0;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f; } bool cmp(poi a,poi b){return a.z<b.z;} int gf(int x){return fa[x]==x?x:gf(fa[x]);} void dfs(int w,int x,int dep) { if(dep>num[w])return; if(x>r[w]){if(dep==num[w])sum++;return;} int xx=gf(a[x].x),yy=gf(a[x].y); if(xx!=yy)fa[xx]=yy,dfs(w,x+1,dep+1),fa[xx]=xx; dfs(w,x+1,dep); } int main() { read(n);read(m); for(int i=1;i<=m;i++)read(a[i].x),read(a[i].y),read(a[i].z); sort(a+1,a+1+m,cmp); for(int i=1;i<=m;i++) { if(a[i].z!=a[i-1].z)r[cnt++]=i-1,l[cnt]=i; a[i].pos=cnt; } r[cnt]=m; for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=m;i++) { int x=gf(a[i].x),y=gf(a[i].y); if(x!=y)fa[x]=y,num[a[i].pos]++,cntt++; } if(cntt!=n-1)return puts("0"),0; for(int i=1;i<=n;i++)fa[i]=i;ans=1; for(int i=1;i<=cnt;i++) if(num[i]) { sum=0;dfs(i,l[i],0); for(int j=l[i];j<=r[i];j++)fa[gf(a[j].x)]=gf(a[j].y); ans=1ll*ans*sum%mod; } printf("%d ",ans); }