题解：P10013 [集训队互测 2023] Tree Topological Order Counting

Guosn · 2025-08-19 11:24:49 · 题解

前置芝士

将 k 个数插入到 m 个数中，方案数为 \binom{m + k}{k}，相当于从 m + k 个数中拿 k 个。
一棵树的拓扑序个数是 n!\over \prod sz_u。对于一棵树有 n! 种的排列，因为对于一个点 u 他必须在它子树内的点前面，所以只有 sz_u-1! 种的排列，相当于除以 sz_u，从根往下递归，总共除以 \prod sz_u
题解

下文中所指 u 的子树含 u。

发现一个点的拓扑序，只与他的父亲有关，所以考虑从上往下转移。设 f_{u,i}，表示不考虑 u 子树内的点，其他点都已经考虑完了，u 的拓扑序是 i 的方案数。

DP 转移：
当从 f_{u,j} 转移到 f_{v,i} 时，要将除了 v 以外的拓扑序安排好，相当将 sz_u-sz_v-1 个点（u 已经安排好了），插入到已经确定的 n - sz_u + 1 个拓扑序中，但又因为子树的拓扑序比 u 的大，所以只有 n - sz_u + 1 -j 个点可以插，插完后再分配拓扑序。
即（其中 k 是 v 子树以外的节点）：

f_{v,i} = \sum_{j = 1} ^{i - 1} f_{u,j} \times \binom{n - sz_u - j + 1 + sz_u-sz_v-1}{sz_u-sz_v-1}\times \frac{(sz_u - sz_v - 1)!}{\prod sz_k}

化简后：

f_{v,i} = \sum_{j = 1} ^{i - 1} f_{u,j} \times \binom{n -sz_v- j}{sz_u-sz_v-1}\times \frac{(sz_u - sz_v - 1)!}{\prod sz_k}

统计答案：
计算点 i 的答案时，要将其子树内 sz_i - 1 的点插入到已经确定的 n - sz_i + 1 个已经确定的拓扑序种，而且还要比 i 的拓扑序大，故（v 是 u 子树内的点）：

ans_i = \sum_{j = 1} ^n b_j\times f_{i,j}\times \binom{n - sz_i + 1 - j + sz_i - 1}{sz_i - 1} \times \frac{sz_i!}{\prod sz_v}

化简：

ans_i = \sum_{j = 1} ^n b_j\times f_{i,j}\times \binom{n - j}{sz_i - 1} \times \frac{sz_i!}{\prod sz_v}

时间复杂度 O(n^3) 考虑优化：f_{v,i} 只比 f_{v,i - 1} 多了 f_{u,i - 1} \times \binom{n -sz_v- (i - 1)}{sz_u-sz_v-1}\times \frac{(sz_u - sz_v - 1)!}{\prod sz_k} 可以前缀和优化。
时间复杂度 O(n^2)。
注意，要判断数组越界，组合数要取模（可能很大）。

code

#include<bits/stdc++.h>
#define N 5010
#define int long long
#define pb push_back
#define md 1000000007
#define Fo(a, b) for(auto a : b) 
#define fo(a, b, c) for(int b = a; b <= c; b++)
#define _fo(a, b, c) for(int b = a; b >= c; b--)
using namespace std;
int n, b[N], fac[N], sz[N], prod[N], C[N][N], f[N][N], ans[N];
vector<int>G[N]; 
int fast(int a, int p){
    int s = 1;
    while(p){
        if(p & 1) s = s * a % md;
        a = a * a % md;
        p >>= 1;
    }
    return s;
}
void init(){
    fac[0] = 1;
    fo(1, i, 5000) fac[i] = fac[i - 1] * i % md; 
    fo(0, i, n) C[i][0] = 1;
    fo(1, i, n) fo(1, j, i) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % md;
    prod[0] = 1, f[1][1] = 1;
}
void dfs(int u){
    sz[u] = prod[u] = 1;
    Fo(v, G[u]){
        dfs(v); 
        sz[u] += sz[v], prod[u] = prod[u] * prod[v] % md; 
    }
    prod[u] = prod[u] * fast(sz[u], md - 2) % md;
}
void calc(int v, int u){
    int tp = fac[sz[u] - sz[v] - 1];
    Fo(cur, G[u]){
        if(v == cur) continue;
        tp = tp * prod[cur] % md;
    }
//  cout << "u;" << u << ' ' << "v:" << v << ' ' << "tp:" << tp << "\n";
    fo(1, i, n){
        if(n - sz[v] - i + 1 >= 0) f[v][i] = (f[v][i - 1] + f[u][i - 1] * C[n - sz[v] - i + 1][sz[u] - sz[v] - 1] % md * tp % md) % md;
    }
}
void solve(int u){
    Fo(v, G[u]){
        calc(v, u), solve(v);
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    fo(2, i, n){
        int fa; cin >> fa;
        G[fa].pb(i);
    }
//  fo(1, i, n){
//      Fo(v, G[i]) cout << v << ' ';
//      cout << "\n";
//  }
    fo(1, i, n) cin >> b[i];
    init();
    //cout << C[4][2] << ' ';
    dfs(1), solve(1);
    //fo(1, i, n) cout << prod[i] << ' '; 
    fo(1, i, n) fo(1, j, n) 
        if(n >= j) ans[i] = (ans[i] + b[j] * f[i][j] % md * C[n - j][sz[i] - 1] % md * fac[sz[i]] % md * prod[i] % md) % md;
    fo(1, i, n) cout << ans[i] << ' ';
    return 0;
}