ICPC南京2024

C. Topology

考虑没有限制怎么做,对于每个点分配 $$ (siz_x-1)! \prod \frac{1}{siz_v!}$$ 转化为子问题乘起来即可

如果 \(k\) 要放在 \(k\) ,我们从下往上放,对于 \(k\) 的子树先乘上\(\C_{n-i}^{siz_x}\),接着乘上子树对应的系数,使k的子树全都确定了

对于父节点 \(f\) 放在p 需要乘上\(C_{n-p-siz_k-1}^{siz_f - 1 -siz_k}\) 乘上其它对应结点的转移系数,重复这个操作即可

容易发现这个转移只需要知道 \(f,p,k\) 即可,我们不妨设 \(f_{ij}\) 表示第 i 个节点放在第j个位置转移时我们就可以乘上系数,直接转移是 \(n^3\) 的,用前缀和优化可以做到 \(n^2\)

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int mod = 998244353;
const int N = 5005;
int n ;
vector<int>gra[N];
int fa[N];
ll f[N][N],h[N];
ll fac[N],ifac[N];
ll g[N];
int siz[N];
ll ans[N];
ll C(int n,int m){
    if(n < 0 || m > n || m < 0) return 0;
    return fac[n] * ifac[m] % mod * ifac[n-m] %mod;
}

ll qpow(ll a,ll b=mod-2){
    ll ans = 1;
    for(;b;b>>=1,a=a*a%mod) if(b&1) ans = ans * a %mod;
    return ans;
}

void init(){
    fac[0] = 1;
    for(int i=1;i<N;i++) fac[i] = fac[i-1] * i % mod;
    ifac[5000] = qpow(fac[5000]);
    for(int i=5000-1;i>=0;i--) ifac[i] = ifac[i+1] * (i+1) %mod;
}


void dfs(int x){
    siz[x] = 1;
    h[x] = 1;
    for(auto v:gra[x]){
        dfs(v);
        siz[x] += siz[v];
        h[x] = h[x] * h[v] % mod;
        h[x] = h[x] * ifac[siz[v]] % mod; 
    }
    h[x] = h[x] * fac[siz[x]-1] % mod;
}

void solve(int x){
    if(x!=1){ 
        memset(g,0,sizeof g);
        int dad = fa[x];
        ll w1 = fac[siz[dad]-1-siz[x]];
        for(auto v:gra[dad]){
            if(v==x) continue;
            w1 = w1 * ifac[siz[v]] % mod;
            w1 = w1 * h[v] % mod ;
        }
        
        for(int j=1;j<=n;j++){
            ll w2 = C(n-j-siz[x],siz[dad] - siz[x] - 1);
            g[j] = f[dad][j] * w2 % mod;
            g[j] = (g[j] + g[j-1] ) %mod;
        }
        for(int j=1;j<=n;j++) f[x][j] = g[j-1] * w1 %mod; 
    }
    ans[x] = f[x][x] * C(n-x,siz[x]-1)  % mod;
    ans[x] = ans[x] * h[x] %mod;
    for(auto v:gra[x]) solve(v);
    
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    init();
    cin >> n;
    for(int i=2;i<=n;i++){
        cin >> fa[i];
        gra[fa[i]].emplace_back(i);
    }
    dfs(1);
    f[1][1] = 1;
    solve(1);
    for(int i=1;i<=n;i++) cout << ans[i] << " ";

    return 0;
}