【题解？】P3523 - 常数优化
题解 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 问题中。