2023-08-08 23:00:07 solution
题意：
求有多少个有 \(n\) 个节点的无向图，使其满足以下条件：
- 无重边自环。
- 有且只有一个最小生成树，且为给定树。
- 最大边权不大于 \(S\)。
对 \(998244353\) 取模。
思路：
其实就是让我们在给定的树加边使得最小生成树不改变。
考虑到在整棵树上我们可以加大于最大边权的任意边使得满足条件，那显然我们断掉最大边后，在各个联通块内随意加大于连通块最大边的边也可以满足条件。
那么我们可以先按照边权将所有边排序，一条一条加入边将节点合并。现在我们先考虑对于两个大小分别为 \(siz_x,siz_y\) 的连通块，用目前最大边 \(w\) 合并，对答案的贡献。
因为 \(x,y\) 内部的贡献已经算过了，所以合并之后显然我们最多只能在 \(x,y\) 之间新增 \(siz_x\times siz_y-1\) 条边，按照上面的理论，每条选了的边可以选 \(S-w\) 个边权，我们令 \(siz_x\times siz_y-1=m\)，那么贡献就为：
\[\binom{m}{0}(S-w)^0+\binom{m}{1}(S-w)^1+\dots+\binom{m}{m}(S-w)^{m}
\]
这显然是一个二项式定理的形式，所以可以将其转化为 \((S-w+1)^m\)。
最后将所有贡献相乘即可。
\(Code\)
struct edge{
int u,v;ll w;
inline bool operator <(const edge &o)const{return w<o.w;}
}F[200005];
int T,n,fa[200005];
ll fac[200005],ifac[200005],siz[200005],S;
inline int find(int x){return (x==fa[x]?x:(fa[x]=find(fa[x])));}
inline int merge(int x,int y){
if((x=find(x))==(y=find(y)))return siz[x];
if(siz[x]>siz[y])x^=y^=x^=y;
siz[y]+=siz[x],siz[x]=0,fa[x]=y;
return siz[y];
}
ll qpow(ll x,ll w){
ll res=1;
for(;w;w>>=1,x=x*x%mod)if(w&1)res=res*x%mod;
return res;
}
int main(){
for(T=read();T--;){
n=read(),S=read();
fa[n]=n,siz[n]=1;
for(int i=1;i<n;i++){
fa[i]=i,siz[i]=1;
int u=read(),v=read(),w=read();
F[i]={u,v,w};
}
sort(F+1,F+n);
ll ans=1;
for(int i=1;i<n;i++){
int u=find(F[i].u),v=find(F[i].v);
ll sume=siz[u]*siz[v]-1;//可以加入的边数
ll sum=qpow(S-F[i].w+1,sume);//二项式定理
ans=ans*sum%mod;
merge(u,v);
}
printf("%lld\n",ans);
}
}