【ICPC2022济南站】【树形dp】【删物品背包dp】C.DFS Order 2

【题意】

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

【思路】

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

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

而对于dp2数组，我们需要在处理dp数组前就提前dfs一次先得到它。设$u$总共有$cnt$个儿子，考虑$u$子树内所有可能的dfs序，转移显然：
$$dp2[u]=cnt!\ast \prod dp2[v]$$
此时，第$i$个点出现在dfs序中第$j$个位置的方案数就是$dp[i][j-1]\ast dp2[i]$。
参考代码：（比赛时写的代码）

#include
#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";
	}
		
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89