本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-02-12 14:32:32

题解 P3523 - 复杂度（常数）优化

如果你被卡了 TLE 或者代码非常慢，请看过来！！！

题目描述

题目 P3523 要求我们在一棵树上选择若干个节点，使得每个关键点到最近选择的节点的距离不超过某个值。

简述做法

本题思路其他题解都已经基本讲的非常清楚，就是外层二分出距离并通过 DP 去 check 可行性。

但是相信很多大佬都面临了 TLE 的问题。 ~~呜呜呜~~。

耗费了一中午卡常，最终在我将 vector 邻接表存图 改为 链式前向星存图 之后，终于过了！而且快了~~不止一点~~好像并不多。

两种方法提交记录

vector 邻接表

链式前向星

难道这就是最优办法了吗？？？——显然不是的。

****那么接下来****

进入正题

在经过 @KSCD_ 及 @ryp 大神指点后，我们发现，vector做法之所以会被卡，很多的时间都花费在了 DFS 及 DP 时 vector 查找合并上面，所以我们考虑如何优化 DFS 及 DP 的过程。

我们可以先进行一遍 DFS，在图上跑出 DFN 序，随后我们在 DP 合并的时候就不需要递归的高时间消耗，转而变成了对数组元素的访问与修改，通过这种方法即可优化掉我们代码中 DFS 递归带来的常数。

此种做法从本质上来讲并没有和其他做法有什么区别，但是这种做法可以通过 减少递归 从而显著优化了树上问题的常数。这样的优化常数在树上进行 DP 的方法也值得研究学习。

这种做法即使使用 vector 并且不卡常也可以通过，并且跑得飞快。大部分的树形 DP 也都可以考虑通过按照 DFN 方合并式来减小常数优化复杂度

代码解析

首先我们跑出图上的 DFN 序，并存储 DFN 对应节点编号。

void dfs(int u,int fat)\/\/fat表示父亲
{
	fa[u] = fat;
	p[++cnt] = u;
	for(int v : G[u])
	{
		if(v == fat) continue;
		dfs(v,u);
	}
}

随后我们就可以在数组里进行 DP。

我们先对 f 数组及 g 数组赋上初始值。

for(int i = 1;i <= n;i++)
  {
  	f[i] = (vis[i] ? 0 : -inf);\/\/f[i] 表示 以i为根的子树中最远的未被覆盖的关键点距离
  	g[i] = inf;\/\/g[i] 表示 以i为根的子树中最近的选择的节点距离
  }

然后就可以直接倒序枚举 DFN 序，即可从叶子向根进行 DP

for(int i = n;i >= 1;i--)
	{
		int u = p[i];
		if(f[u] + g[u] <= x) f[u] = -inf;
		if(f[u] == x)
		{
			ct++;
			f[u] = -inf;
			g[u] = 0;
		}
		f[fa[u]] = max(f[fa[u]],f[u] + 1);
		g[fa[u]] = min(g[fa[u]],g[u] + 1);
	}

最后是完整代码及提交记录（个人认为在加强数据之后算是跑的比较快的~）

AC记录

代码

#include<bits\/stdc++.h>
using namespace std;
#define endl '\n'
const int maxn = 3e5 + 10;
const int inf = 0x3f3f3f3f;
int vis[maxn],fa[maxn],f[maxn],g[maxn];
int n,k;
int p[maxn];
int cnt;
vector<int> G[maxn];
void dfs(int u,int fat)
{
	fa[u] = fat;
	p[++cnt] = u;
	for(int v : G[u])
	{
		if(v == fat) continue;
		dfs(v,u);
	}
}

bool check(int x)
{
	int ct = 0;
	for(int i = 1;i <= n;i++)
	{
		f[i] = (vis[i] ? 0 : -inf);
		g[i] = inf;
	}
	for(int i = n;i >= 1;i--)
	{
		int u = p[i];
		if(f[u] + g[u] <= x) f[u] = -inf;
		if(f[u] == x)
		{
			ct++;
			f[u] = -inf;
			g[u] = 0;
		}
		f[fa[u]] = max(f[fa[u]],f[u] + 1);
		g[fa[u]] = min(g[fa[u]],g[u] + 1);
	}
	if(f[1] >= 0) ct++;
	return (ct <= k);
}
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	for(int i = 1;i <= n;i++)
	{
		cin >> vis[i];
	}
	for(int i = 1;i < n;i++)
	{
		int u,v;
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1,0);
	int l = 0,r = n;
	int ans = n;
	while(l <= r)
	{
		int mid = (l + r) >> 1;
		if(check(mid)) ans = mid,r = mid - 1;
		else l = mid + 1;
	}
	cout << ans << endl;
	return 0;
}

总结

通过使用链式前向星和 DFN 序，我们成功优化了树形 DP 的常数，使得算法能够在更短的时间内通过本题。这种方法不仅适用于本题，还可以推广到其他树形 DP 问题中。

xuyunao 的博客

博客