题解：P10013 [集训队互测 2023] Tree Topological Order Counting
george0929
·
·
题解
树上 DP 好题。
DP 状态
和顺序有关的问题，在 DP 状态设计时，如果整体不好考虑，可以考虑当前 DP 完的集合在离散化后的状态，转移时乘上组合数。
转移方向自上而下。
### 答案计算
**子问题 $1$**：一个离散化的整数序列，大小为 $m$，插入 $k$ 个有序数字的方案数是多少？
解答：逆向考虑，相当于从大小为 $m+k$ 的序列中选 $k$ 个分裂出来，答案为 $\binom{m+k}{k}$。
**子问题 $2$**：一个树的总共拓扑序个数是多少？
解答：我们有现成的结论，一个树的拓扑序个数为 $\frac{n!}{\prod_{i=1}^{n} sz_i}$。
则答案计算如下：
$$ans_i=\sum\limits_{j=1}^n b_j\times f_{i,j}\times \underbrace{\binom{(n-sz_i-j+1)+(sz_i-1)}{sz_i-1}}_{\text{第一部分}}\times \underbrace{\frac{sz_i!}{\prod_{k\in subtree(i)} sz_k}}_{\text{第二部分}}$$
第一部分解释：将大小为 $sz_i-1$ 的子树拓扑序插入到比 $i$ 拓扑序大的 $n-sz_i-j+1$ 个已经确定拓扑序的节点中。
第二部分解释：分配 $i$ 子树内部拓扑序。
维护 $g_u=\prod_{k\in subtree(u)} sz_k$，即可 $O(n^2)$ 计算答案。
### 初始值
$f_{1,1}=1$。
### 转移方程
设 $u$ 是 $v$ 的父节点，$u\to v$ 的转移如下：
$$f_{v,i}=\sum\limits_{j=1}^{i-1} f_{u,j}\times \underbrace{\binom{(n-sz_u+1-i)+(sz_u-sz_v-1)}{sz_u-sz_v-1}}_{\text{第一部分}}\times \underbrace{\frac{(sz_u-sz_v)!}{\prod\limits_{x\in subtree_u\land x\notin subtree_v} sz_x}}_{\text{第二部分}}$$
第一部分解释：将子树 $u$ 除去子树 $v$ 后的其他节点（不含 $u$）的拓扑序（大小为 $sz_u-sz_v-1$）插入到比 $u$ 拓扑序大的 $n-sz_u+1-i$ 个已经确定拓扑序的节点中。
第二部分解释：分配子树 $u$ 除去子树 $v$ 外的其他节点的拓扑序。
第二部分可表示为 $\frac{(sz_u-sz_v)!}{g_u\div g_v\div sz_u\times (sz_u-sz_v)}$。
前缀和优化后时间复杂度 $O(n^2)$。
### 代码实现
分两次 dfs，第一次算 $sz$ 和 $g$，第二次算 $f$。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int ksm(int a,int b){
int res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b/=2;
}
return res;
}
int fac[10005],Ifac[10005];
void init(){
const int V=1e4;
fac[0]=1;
for(int i=1;i<=V;i++) fac[i]=fac[i-1]*i%mod;
Ifac[V]=ksm(fac[V],mod-2);
for(int i=V-1;i>=0;i--) Ifac[i]=Ifac[i+1]*(i+1)%mod;
}
int C(int n,int m){
if(n<0||m<0||n<m) return 0;
return fac[n]*Ifac[m]%mod*Ifac[n-m]%mod;
}
//----------------
int n,b[5005];
vector<int> V[5005];
int f[5005][5005];
int sz[5005],g[5005];
void dfs1(int u){
sz[u]=g[u]=1;
for(int v:V[u]){
dfs1(v);
sz[u]+=sz[v];
g[u]=g[u]*g[v]%mod;
}
g[u]=g[u]*sz[u]%mod;
}
void dfs2(int u){
int invg=ksm(g[u],mod-2);
for(int v:V[u]){
int invsz=ksm(sz[u]-sz[v],mod-2);
for(int i=1;i<=n-sz[v]+1;i++){
f[v][i+1]=f[u][i]*C(n-sz[u]+1-i+sz[u]-sz[v]-1,sz[u]-sz[v]-1)%mod;
f[v][i+1]=f[v][i+1]*fac[sz[u]-sz[v]]%mod*g[v]%mod*invg%mod*sz[u]%mod*invsz%mod;
f[v][i+1]=(f[v][i+1]+f[v][i])%mod;
}
dfs2(v);
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
init();
cin>>n;
for(int i=2;i<=n;i++){
int p;
cin>>p;
V[p].push_back(i);
}
for(int i=1;i<=n;i++) cin>>b[i];
dfs1(1);
f[1][1]=1;
dfs2(1);
for(int i=1;i<=n;i++){
int ans=0;
int invg=ksm(g[i],mod-2)%mod;
for(int j=1;j<=n;j++){
int res=b[j]*f[i][j]%mod;
res=res*C(n-sz[i]-j+1+sz[i]-1,sz[i]-1)%mod;
res=res*fac[sz[i]]%mod*invg%mod;
ans=(ans+res)%mod;
}
cout<<ans<<" ";
}
return 0;
}
```