自动搬运

查看原文

来自洛谷，原作者为

	9981day AFO

搬运于2025-08-24 22:50:35，当前版本为作者最后更新于2023-10-25 17:17:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P9669 [ICPC2022 Jinan R] DFS Order 2 题解

简要题意

给定一棵 $n$ 个节点的树，根节点是 $1$。

从根节点开始深度优先搜索这一棵树，dfs 序是在搜索过程中访问节点的顺序。

对于每一个节点 $v$，你要给出有多少种不同的 dfs 序，使得 $v$ 出现在第 $j$ 个位置。

答案对 $998244353$ 取模。

解法说明

首先我们考虑一下总共有多少种 dfs 序。

记 $h[x]$ 为只考虑 $x$ 的子树内的节点所形成的 dfs 序的方案数。

假设 $x$ 有 $m$ 个儿子，那么他选第一个儿子的时候有 $m$ 种选法，第二个儿子有 $m - 1$ 种选法，同理第 $i$ 个儿子有 $m - i + 1$ 种选法，那么他儿子的选法总共有 $m!$ 种。

然后再乘上他每个儿子的只考虑子树内节点形成 dfs 序的方案数。

我们可以得到 $h[x] = jc[m]\times\prod\limits_{v \in e[x].v} h[v]$。

其中 $jc[i]$ 表示 $i$ 的阶乘，$e[x].v$ 表示 $x$ 的儿子节点。

设 $f[j][k]$ 表示在 $x$ 的儿子中选了 $j$ 个儿子，$s$ 和为 $k$ 的方案数。

其中 $s[x]$ 表示 $x$ 的子树中的总节点数。

$f[j][k]$ 可以通过背包的方式来求出。

每一个 $j \in [1,m],k \in [s[v],n]$ 由 $f[j - 1][k - s[v]],v \in e[x].v$ 转移而来。

因为我们把表示 $x$ 的那一维滚掉了，所以我们需要逆序来算上面的 $f[j][k]$。

然后我们假设我们现在已经处理到 $x$ 的儿子 $v$ 这个节点。

设 $g[k]$ 表示当前儿子节点 $v$ 排在 $x$ 后面 $k$ 个位置的方案数，$hx$ 为该节点除去儿子 $v$ 的方案以及去掉选 $m$ 个儿子的排列的方案。

我们知道 $f[j][k]$ 是 $x$ 的儿子中的总方案数，为了求出 $v$ 节点排在父亲后的方案,我们需要求出除去 $v$ 的方案数。

可以通过回退背包的做法，把 $v$ 的贡献减掉。

对于每个状态 $f[j][k]$ 我们把 $f[j - 1][k - s[v]]$ 的贡献给减掉，上面加入贡献我们是逆序做的，这里需要正序来减。

总的方案每一次计算新的 $v$ 都要使用，所以在这次的关于 $v$ 的计算完成后，要把这里减掉的贡献重新加回去。

对于选择的节点数量 $k \in [1,s[x]]$ 可以由不同的儿子节点的选择方式组成，那么 $g[x]$ 可以从 $f[j][k]$ 转移过来。

对于已选的 $j$ 个儿子，有 $j!$ 种选择，剩下的 $m - j - 1$ 个儿子，有 $(m - j - 1)!$ 种选择。

然后再乘上 $hx$ 就可以得到 $g[x]$。

这里的 $hx = \frac{h[x]}{h[v] \times m!}$ 是去除 $v$ 的子树中，$x$ 的子树中，其他节点的方案数。

现在我们求出了儿子节点排在父亲节点后 $k$ 个位置的方案数了，那么我们便可以推出他在整棵树中 dfs 序的情况了。

设 $dp[x][k]$ 表示 $x$ 在总的 dfs 序中排在位置 $k$ 的方案数（不计 $x$ 子树内部节点方案数）。

每个儿子节点的位置都可以从他父亲的位置往后推出来，即 $dp[v][j + k] = \sum\limits_{j\in[1,n],k\in[1,s[x]]} dp[x][j] \times g[k]$。

然后 $dp[i][j] \times h[i]$ 即为题目要求的最终的方案数。

我们对于每一个节点 $x$ 都要求一个 $f[j][k]$，每个 $f[j][k]$ 都需要遍历 $x$ 的儿子数以及所有的叶子节点数，这里的复杂度是 $O(n^3)$ 的。

同理其他几个状态的转移复杂度和这个也是同级的，所以总复杂度为 $O(n^3)$。

原本对于每个 $x$ 的每个 $v$ 单独求解除去 $v$ 的方案应该是 $O(n^4)$ 的复杂度，这里使用了回滚背包，优化成了 $O(n^3)$。

具体实现

#include<bits/stdc++.h>

#define int long long

using namespace std;

int read()
{
	int s = 0,f = 1; char x = getchar();
	while(x < '0' || '9' < x) f = (x == '-') ? -1 : 1 , x = getchar();
	while('0' <= x && x <= '9') s = s * 10 + x - '0' , x = getchar();
	return s * f;
}

const int N = 510;
const int mo = 998244353;

int n;
int s[N],ft[N];
int h[N],son[N];
int f[N][N];
int ans[N][N],dp[N][N];
int iv[N],fc[N];

vector <int> e[N];

int fpow(int x,int nn)
{
	int res = 1;
	while(nn)
	{
		if (nn & 1) res = (res * x) % mo;
		x = (x * x) % mo;
		nn >>= 1;
	}
	return res;
}

int inv(int x)//求逆元
{
	if (x <= n) return (iv[x] * fc[x - 1]) % mo;
	return fpow(x,mo - 2);
}

void dfs(int x,int fa)
{
	ft[x] = fa;
	s[x] = 1;
	h[x] = 1;
	for (int i = 0,v;i < e[x].size();i ++)
	{
		v = e[x][i];
		if (v == fa) continue;
		son[x] ++;
		dfs(v,x);
		h[x] = (h[x] * h[v]) % mo;//在x的子树内的方案数
		s[x] += s[v];
	}
	h[x] = (h[x] * fc[son[x]]) % mo;
	return;
}

void dfs1(int x)
{
	int m = son[x];
	vector<vector<int> > f(m + 1,vector<int>(s[x] + 1,0));
	f[0][0] = 1;//不选儿子一种方案
	for (int i = 0,v;i < e[x].size();i ++)
	{
		v = e[x][i];
		if (v == ft[x]) continue;
		for (int j = m;j >= 1;j --)
		{
			for (int k = s[x];k >= s[v];k --)
			{
				f[j][k] = (f[j][k] + f[j - 1][k - s[v]]) % mo;//选v这个儿子
			}
		}
	}
	
	for (int i = 0,v;i < e[x].size();i ++)
	{
		v = e[x][i];
		if (v == ft[x]) continue;
		
		int hx = (h[x] * inv(h[v]) % mo * iv[m]) % mo;//去掉儿子中v的方案数以及去掉 选m个儿子的排列的方案

		for (int j = 1;j <= m;j ++)
			for (int k = s[v];k <= s[x];k ++)
				f[j][k] = ((f[j][k] - f[j - 1][k - s[v]]) % mo + mo) % mo;//去掉儿子v的方案数
		
		vector <int> g(n + 1,0);//g[k]表示在x后k个位置的方案数
		
		for (int j = 0;j < m;j ++)
			for (int k = 0;k < s[x];k ++)
				g[k + 1] = (g[k + 1] + f[j][k] * hx % mo * fc[j] % mo * fc[m - j - 1]) % mo;

		for (int j = 1;j <= n;j ++)
			for (int k = 1;k <= s[x];k ++)
				dp[v][j + k] = (dp[v][j + k] + dp[x][j] * g[k]) % mo;
		
		for (int j = m;j >= 1;j --)
			for (int k = s[x];k >= s[v];k --)
				f[j][k] = (f[j][k] + f[j - 1][k - s[v]]) % mo;
		
		dfs1(v);
	}
	return;
}

signed main()
{
	n = read();
	
	fc[0] = 1;
	for (int i = 1;i <= n + 1;i ++) fc[i] = (fc[i - 1] * i) % mo;
	iv[n + 1] = fpow(fc[n + 1],mo - 2);
	for (int i = n;i >= 0;i --) iv[i] = (iv[i + 1] * (i + 1)) % mo;//求阶乘逆元
	
	for (int i = 1,u,v;i < n;i ++)
	{
		u = read() , v = read();
		e[u].push_back(v) , e[v].push_back(u);
	}
	
	dfs(1,0);
	
	dp[1][1] = 1;
	
	dfs1(1);
	
	for (int i = 1;i <= n;i ++)
	{
		for (int j = 1;j <= n;j ++)
		{
			ans[i][j] = (dp[i][j] * h[i]) % mo;
			cout << ans[i][j] << ' ';
		}
		puts("");
	}
	return 0;
}

后话

这篇题解主要是参考了 2022 International Collegiate Programming Contest, Jinan Site C. DFS Order 2(树形dp+回滚背包) 和 2022 ICPC 济南站 C (回退背包) 还有 P9669 [ICPC2022 Jinan R] DFS Order 2 三位大佬的题解。