传送门

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