G | 小月的炼金术

对于类型为 的边，令其边权为 ；对于类型为 的边，令其边权为 ；对于类型为 的边，令其边权为 。

那么我们对这个图做矩阵树定理，求出来的 即代表 的所有生成树的 之和。

将这个多项式乘以 ，则是一个 次多项式，直接代入 作为点值做矩阵树然后拉插出原多项式即可，时间复杂度 。

void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) g[i][j]=-1;
    }
    for(int i=1,u,v;i<=m;i++) cin>>u>>v,cin>>w[u][v]>>g[u][v],g[v][u]=g[u][v],w[v][u]=w[u][v];
    for(int x=1;x<=n*2+1;x++){
        mat.init(n);
        int iv=inv(x);
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if(g[i][j]==0) mat.link(i,j,w[i][j]*x%mod);
                if(g[i][j]==1) mat.link(i,j,w[i][j]*iv%mod);
                if(g[i][j]==2) mat.link(i,j,w[i][j]);
            }
        }
        xx.pb(x),yy.pb(mat.calc()*quickpow(x,n)%mod);
    }
    vector<int> res=work(2*n+1,xx,yy);
    int sum=0;
    for(int i=n;i>=0;i-=3) sum=(sum+res[i])%mod;
    for(int i=n+3;i<=2*n;i+=3) sum=(sum+res[i])%mod;
    cout<<sum<<endl;
}