题解：P15578 [USACO26FEB] Random Tree Generation G

· · 题解

第一步随机得到的树必然满足父亲的编号小于儿子这个条件。

第二步随机的意义就是将第一步的树的编号用一个排列 p_i 替换。我们可以找到一个排列 q 使得 q_{p_i}=i，并且每一个 p 都唯一对应一个 q。我们知道第二步随机之后得到的树，那么我们用 q 替换就能得到第一步的树。

对这类树计数，最后除以总方案数 n!(n-1)! 就是答案。

不妨先指定一个根，设 f_i 为 i 子树内满足父亲的编号小于儿子且所有点编号都在 1 到 sz_i 之间的树的方案数，sz_i 为 i 子树的大小。那么我们只关心相对顺序。显然此时 i 的编号必须为 1，然后对于每一个儿子 u，我们在剩下的位置里选 sz_u 个，按相对顺序填入 u 子树的节点，就可以不重不漏地得到当前子树的方案。

也就是说，

f_o = (sz_o-1)!\prod_{i \in \mathrm{son}(o)} \frac{f_i}{sz_i!}

。

对于每一个点，钦定它是根，算出来的 f_i 都对应不同的方案（因为编号为 1 的点的位置不同了）。全部相加就是总方案。上面的式子换根很方便，换根 dp 求出以每一个点为根的答案相加即可。

:::info{Code Time}

#include <bits/stdc++.h>
using namespace std;
const int N=1000007,mod=1000000007;
int fa[N],fi[N],f[N],sz[N],ans;
vector<int> to[N];
int inv(int x){
    int ans=1,b=mod-2;
    for(;b;b>>=1,x=1ll*x*x%mod) if(b&1) ans=1ll*ans*x%mod;
    return ans;
}
void dfs(int o,int p){
    sz[o]=1;
    for(auto i:to[o]) if(i!=p) dfs(i,o),sz[o]+=sz[i];
    f[o]=fa[sz[o]-1];
    for(auto i:to[o]) if(i!=p) f[o]=1ll*f[o]*f[i]%mod*fi[sz[i]]%mod;
}
void calc(int o,int p){
    ans=(ans+f[o])%mod;
    for(auto i:to[o]) if(i!=p){
        int bfo=f[o],bso=sz[o],bfi=f[i],bsi=sz[i]; // 备份可能用到的数。
        f[o]=1ll*f[o]*fi[sz[o]-1]%mod*inv(f[i])%mod*fa[sz[i]]%mod;
        sz[o]-=sz[i];
        f[o]=1ll*f[o]*fa[sz[o]-1]%mod;
        f[i]=1ll*f[i]*fi[sz[i]-1]%mod; // 换根的通法：将 o 的一个儿子 i 的贡献去掉，然后把 i 加上 o 的贡献，dfs，最后还原。
        sz[i]+=sz[o];
        f[i]=1ll*f[i]*fa[sz[i]-1]%mod*f[o]%mod*fi[sz[o]]%mod;
        calc(i,o);
        f[o]=bfo,sz[o]=bso,f[i]=bfi,sz[i]=bsi;
    }
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    fa[0]=1;
    for(int i=1;i<N;i++) fa[i]=1ll*i*fa[i-1]%mod;
    fi[N-1]=inv(fa[N-1]);
    for(int i=N-1;i;i--) fi[i-1]=1ll*i*fi[i]%mod;
    int t;
    cin>>t;
    while(t-->0){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++) to[i].clear(); // 多测要清空。
        for(int i=1,u,v;i<n;i++) cin>>u>>v,to[u].push_back(v),to[v].push_back(u);
        ans=0;
        dfs(1,0);
        calc(1,0);
        cout<<1ll*ans*fi[n]%mod*fi[n-1]%mod<<'\n'; //求的是概率，记得除以总方案数。
    }
    return 0;
}

:::