Bientôt исчезать の happiness.
显然，不同的$MST$，每种边权的出现次数是相同的。而把某个边权从不同的$MST$中删去，得到的联通块形态一样的。
对后者的简单证明：任求一棵$MST$，删去某个边权$x$。对剩下的联通块，假设存在一条长为$y$的边能连接两个联通块。若$y< x$，存在更优的$MST$，不符合当前树是$MST$；若$y>x$，连起来得到的比当前树劣，不可能连这条边。
于是就可以随便搞个$MST$，枚举边权，把$MST$中不是该边权的边连起来，对得到的联通块们和原图中所有等于该边权的边跑矩阵树定理，根据乘法原理乘起来就是答案。
分析一波复杂度是$O(n^3\log n)$的。
代码：
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #define maxn 105 #define inf 0x3f3f3f3f const int mod = 31011; using namespace std; inline int read(){ int x=0,y=0; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();} while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return y?-x:x; } int a[maxn][maxn],fa[maxn],id[maxn],cnt,n,m; struct edge{ int x,y,l; bool operator < (const edge &a)const{return l<a.l;} }e[maxn*10],u[maxn]; int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} inline void add(int x,int y){++a[x][x],++a[y][y],--a[x][y],--a[y][x];} void kru(){ sort(e+1,e+1+m); for(register int i=1;i<=n;++i)fa[i]=i; for(register int i=1;i<=m;++i){ int x=find(e[i].x),y=find(e[i].y); if(x==y)continue; u[++cnt]=e[i],fa[x]=y; } } int Gauss(){ int ans=1; for(register int i=2;i<=cnt;++i){ for(register int j=i+1;j<=cnt;++j) while(a[j][i]){ int t=a[i][i]/a[j][i]; for(register int k=i;k<=cnt;++k)(a[i][k]-=a[j][k]*t)%=mod,swap(a[i][k],a[j][k]); ans=-ans; } ans=1ll*ans*a[i][i]%mod; } return ans; } int calc(int l){ cnt=0,memset(a,0,sizeof a); for(register int i=1;i<=n;++i)fa[i]=i,id[i]=0; for(register int i=1;i<n;++i)if(u[i].l!=l)fa[find(u[i].x)]=find(u[i].y); for(register int i=1;i<=n;++i){ int x=find(i); if(!id[x])id[x]=++cnt; id[i]=id[x]; } for(register int i=1;i<=m;++i)if(e[i].l==l&&id[e[i].x]!=id[e[i].y])add(id[e[i].x],id[e[i].y]); return Gauss(); } int main(){ n=read(),m=read(); int ans=1; for(register int i=1;i<=m;++i)e[i].x=read(),e[i].y=read(),e[i].l=read(); kru(); for(register int i=1;i<n;++i)if(u[i].l!=u[i-1].l)ans=1ll*ans*calc(u[i].l)%mod; printf("%d\n",ans); }
