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

树上 DP 好题。

DP 状态

和顺序有关的问题，在 DP 状态设计时，如果整体不好考虑，可以考虑当前 DP 完的集合在离散化后的状态，转移时乘上组合数。

f_{u,i}

表示不考虑子树

u

内部，将

u

和子树

u

外的节点拓扑序离散化后，节点

u

的拓扑序为

i

的方案数。

转移方向自上而下。

答案计算

子问题 $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;
}

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

文章操作

DP 状态

答案计算

初始值

转移方程

代码实现

相关推荐

评论

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