【ICPC2022济南站】【树形dp】【删物品背包dp】C.DFS Order 2-Toy模板网

这篇具有很好参考价值的文章主要介绍了【ICPC2022济南站】【树形dp】【删物品背包dp】C.DFS Order 2。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【题意】

题目链接：https://codeforces.com/gym/104076/problem/C
简要题意：给定一棵n个点的有根树，对于所有的二元组 $(i, j)$ 求这颗树所有可能的dfs序中有多少个dfs序满足第 $i$ 个点出现在dfs序第 $j$ 个位置。

【思路】

~~赛场上假了无数次以后，我终于才理清楚了这题的dp思路。~~
状态定义：
定义 $d p [u] [i]$ 表示只考虑 $u$ 子树外的点的情况下，dfs序中在 $u$ 前面有 $i$ 个点的方案数。注意，这个 $d p$ 值并不能直接作为答案，还要乘上 $u$ 子树内部的所有可能的dfs序方案数。显然这个 $d p$ 的取值与 $u$ 子树的情况无关，因此这道题 $d p$ 的转移与一般树形 $d p$ 不同，这道题应当自上而下用父亲的信息更新儿子的信息。上文提到过，为了得到答案，我们还需要 $u$ 子树内部的dfs序方案数量，因此定义 $d p 2 [u]$ 表示 $u$ 子树内的dfs序方案数。
状态转移：
设我们当前在 $u$ 点，我们考虑更新 $u$ 的一个儿子 $v$ 的 $d p$ 信息，我们需要知道dfs序有多少个点在 $v$ 前面，我们把这些点分为在 $u$ 的子树内和 $u$ 的子树外两类，最后类似背包的思路合并即可。

对于 $u$ 子树外的点的信息，我们通过 $u$ 的 $d p$ 值即可获得；
对于 $u$ 子树内的点，在 $v$ 前面的点的数量取决于 $u$ 的儿子们的排列顺序，我们可以把u的所有儿子的子树大小 $s i z$ 拿来做一次背包，与一般背包不同的是，后续用背包的结果更新dp值时还需要考虑放置顺序，因此我们还需要加一维表示当前背包的大小，便于考虑物品顺序。设 $c [i] [j]$ 表示放置了 $i$ 个物品，总大小为 $j$ 的方案数，考虑放置子树 $v$ ，则转移显然： $c [i] [j] = c^{'} [i] [j] + c^{'} [i - 1] [j - s i z [v]]$
$c^{'}$ 表示未考虑 $v$ 的dp值， $c$ 表示已考虑 $v$ 的dp值，因此 $i$ 这一维倒序枚举更新即可不需要额外的数组。若我们要求 $v$ 的dp值，则我们背包里需要删除 $v$ 这个物品。由于背包dp的本质是一种多项式的卷积(此处的dp等价于 $c(y,x)=\prod_{v\in son_u}(1+y*x^{siz[v]})$ )，放置顺序无关紧要，我们不妨假设 $v$ 是最后一个加入背包的物品。此时相当于我们已知c数组而需要求 $c^{'}$ 数组(注意，这里的 $c^{'}$ 数组在参考代码里就是 $d$ 数组)。移项可得转移：
$c^{'} [i] [j] = c [i] [j] - c^{'} [i - 1] [j - s i z [v]]$
在得到 $c^{'}$ 数组后，设在 $v$ 前面有 $j$ 个 $u$ 子树内的点的方案数为 $b [j]$ ， $u$ 一共有 $c n t$ 个儿子，则有转移：
$b[j]=\sum_{i=0}^{cnt-1} c'[i][j]*i!*(cnt-1-i)!$
而对于 $u$ 这个点，它在dfs序中一定位于其他 $u$ 子树内的点的前面，我们可以在设置 $c$ 数组初值时考虑它，即: $c [0] [1] = 1$ 。
现在，我们已知 $b$ 数组和 $d p$ 数组，考虑用背包dp的思路对它们进行合并。但是我们目前仅考虑了u的儿子之间的排列顺序，尚未考虑这些儿子子树内的排序方案。设 $B=\prod_{x\in son_u}dp2[x]$ 。当我们用这些信息去更新 $v$ 的dp值时，需要注意除去常数B中和 $v$ 子树有关的信息。诚然，不除去这部分信息的话，我们直接得到的就是 $v$ 的答案数组，但是这并不利于我们进一步dfs求v的子树的dp信息，因此我们在这里的处理是除去这部分信息。即定义 $C=\prod_{x\in son_u,x\neq v}=\frac B {dp2[v]}$ ，有以下转移：
$对于i\in [1,n],dp[v][i]=C*\sum_{j=0}^{siz[u]}b[j]*dp[u][i-j]$
（ $j$ 的上确界是小于 $s i z [u]$ 的，比赛时为了求稳所以定枚举上界为 $s i z [u]$ ）

而对于dp2数组，我们需要在处理dp数组前就提前dfs一次先得到它。设 $u$ 总共有 $c n t$ 个儿子，考虑 $u$ 子树内所有可能的dfs序，转移显然：
$dp2[u]=cnt!*\prod dp2[v]$
此时，第 $i$ 个点出现在dfs序中第 $j$ 个位置的方案数就是 $d p [i] [j - 1] * d p 2 [i]$ 。
参考代码：（比赛时写的代码）文章来源地址https://www.toymoban.com/news/detail-638663.html

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=505,mod=998244353;
int n,dp[N][N],siz[N],c[N][N],d[N][N],b[N],fac[N],dp2[N];
vector<int>g[N];
void Add(int&x,int y){
	((x+=y)>=mod)&&(x-=mod);
}
inline int mul(int x,int y){
	return 1ll*x*y%mod;
}
inline int dec(int x,int y){
	return x<y?x-y+mod:x-y;
}
inline int ksm(int a,int b){
	int ret=1;
	while(b){
		if(b&1)ret=mul(ret,a);
		a=mul(a,a);
		b>>=1;
	}return ret;
}
void dfs1(int u,int fa){
	siz[u]=1;
	dp2[u]=1;
	int cnt=0;
	for(int v:g[u]){
		if(v==fa)continue;
		cnt++;
		dfs1(v,u);
		siz[u]+=siz[v];
		dp2[u]=mul(dp2[u],dp2[v]);
	}
	dp2[u]=mul(dp2[u],fac[cnt]);
}
void dfs2(int u,int fa){
	int cnt=0,sum=1;
	memset(c,0,sizeof c);
	c[0][1]=1;
	int lsr=1;
	for(int v:g[u]){
		if(v==fa)continue;
		cnt++;sum+=siz[v];
		lsr=mul(lsr,dp2[v]);
		for(int i=cnt;i>=1;i--)
			for(int j=sum;j>=siz[v];j--)
				Add(c[i][j],c[i-1][j-siz[v]]);
	}
	for(int v:g[u]){
		if(v==fa)continue;
		memset(d,0,sizeof d);
		for(int i=0;i<=cnt;i++)
			for(int j=0;j<=siz[u];j++)
				d[i][j]=dec(c[i][j],(j>=siz[v]&&i>0)?d[i-1][j-siz[v]]:0);
		memset(b,0,sizeof b);
		for(int i=0;i<cnt;i++)
			for(int j=0;j<=siz[u];j++)
				Add(b[j],mul(mul(fac[i],fac[cnt-i-1]),d[i][j]));
		int bas=mul(lsr,ksm(dp2[v],mod-2));
		for(int i=0;i<=n;i++)
			for(int j=0;j<=siz[u];j++)
				Add(dp[v][i+j],mul(bas,mul(dp[u][i],b[j])));
	}
	for(int v:g[u]){
		if(v!=fa)dfs2(v,u);
	}
}
int main()
{
	scanf("%d",&n);
	fac[0]=1;
	for(int i=1;i<=n;i++)fac[i]=mul(fac[i-1],i);
	for(int i=2;i<=n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dp[1][0]=1;
	dfs1(1,0);
	dfs2(1,0);
	for(int i=1;i<=n;i++){
		for(int j=0;j<n;j++)
			cout<<mul(dp[i][j],dp2[i])<<" ";
		cout<<"\n";
	}
		
}