[题解] [SDOI2011] 消防

[题解] [SDOI2011] 消防

tag: 图论、树、树的直径
题目链接（洛谷）：https://www.luogu.com.cn/problem/P2491

题目描述

给定一棵 $n$ 个节点的树，第 $i$ 条边有边权 $z_i$ 。要求找到树上一条长度不大于 $s$ 的简单路径，使得不在路径上的点到该路径的最大距离最小。
数据范围：$1\le n\le 3\times 10^5,0\le z_i\le 10^3$

题解

不难得出结论：如果没有 $s$ 的限制，则选择该树的直径最优。进一步考虑长度为 $s$ 的限制对答案的影响，可以发现即使在限制长度的条件下，答案的路径依然是直径的子集。在此不做严格证明，可以尝试采用在直径上删边、在点上扩展边的方式验证。因此，我们枚举在直径中的路径区间来解决此问题。对于直径，可以使用两次 DFS 的方式求得直径上的所有点，及其中各相邻点之间的距离，这个过程的时间复杂度是 $O(n)$。对于区间枚举，我们使用双指针，从左到右枚举区间的左端点，利用 $l\le s$ 的条件确定右端点即可，这个过程的时间复杂度也是 $O(n)$ 。

那么新的问题是，对于一条确定的直径上的路径，如何求得距离该路径最远的点的距离。我们按照将直径缩短的思路思考。最初始的情况，我们要考虑不在直径上的点到直径的距离，可以利用 DFS ，从每个直径上的点向不在直径上的点遍历，在 $O(n)$ 的时间复杂度内求出每个不在直径上的点到直径的最大值，我们称之为初始最长路径，这些初始最长路径的最大长度就是该问题的初始答案。接下来考虑直径缩短，我们又可以得到一个新的结论：在路径从直径上缩短时，除初始最长路径之外，新的最长路径一定是缩短后的路径的两端到直径的两端的距离的较大值。这个结论也不难验证。因此，我们只需在双指针枚举时动态维护这个长度，同时更新直径上的答案即可。最终的答案是初始答案和直径上的较大值。

AC 代码

//
// Created by wxy3265 on 2024/10/3.
//
#include <iostream>
#include <cstdio>
#include <cstring>
#define int long long
using namespace std;const int MAXN = 2e7 + 5e6;
const int MAXM = 2e7 + 5e6;// 建图
int first[MAXN], v[MAXM], nt[MAXM], w[MAXM];
int te;
inline void addEdge(int x, int y, int ww) {nt[++te] = first[x];first[x] = te;v[te] = y;w[te] = ww;
}// 第一次 DFS 找到直径的一端
int maxd, maxdi;
void dfs1(int x, int fa, int step) {if (step > maxd) maxd = step, maxdi = x;for (int eo = first[x]; eo; eo = nt[eo]) {const int ep = v[eo];if (ep == fa) continue;dfs1(ep, x, step + w[eo]);}
}// 第二次 DFS 找到直径，同时求出直径上相邻点及距离(nxt、nw)
int f[MAXN], nxt[MAXN], nw[MAXN];
void dfs2(int x, int fa, int step) {for (int eo = first[x]; eo; eo = nt[eo]) {const int ep = v[eo];if (ep == fa) continue;dfs2(ep, x, step + w[eo]);if (f[ep] > f[x]) {f[x] = f[ep];nxt[x] = ep;nw[x] = w[eo];}}if (!f[x]) f[x] = step;
}// 第三次 DFS 求出从各直径上的点出发不经过其他直径上的点的最远距离
bool id[MAXN];
int mx[MAXN];
void dfs3(int x, int fa) {for (int eo = first[x]; eo; eo = nt[eo]) {const int ep = v[eo];if (ep == fa || id[ep]) continue;dfs3(ep, x);mx[x] = max(mx[x], mx[ep] + w[eo]);}
}int q[MAXN], head = 0, tail = 0;
signed main() {// 读入数据int n, s;cin >> n >> s;for (int i = 1; i <= n - 1; i++) {int x, y, ww;cin >> x >> y >> ww;addEdge(x, y, ww);addEdge(y, x, ww);}// 求直径dfs1(1, 0, 0);dfs2(maxdi, 0, 0);int tot = 0;head = 1;for (int i = maxdi; i != 0; i = nxt[i]) {q[++tail] = i;tot += nw[i];id[i] = true;}// 求初始答案int r = tail, now = tot, ans = 0, tmp = tot;for (int i = 1; i <= n; i++) {if (id[i]) {dfs3(i, 0);ans = max(ans, mx[i]);}}// 双指针遍历int dr = 0, dl = 0;while (head <= s) {while (r >= head && now > s) {r--;now -= nw[q[r]];dr += nw[q[r]];}tmp = min(tmp, max(dr, dl));dl += nw[q[head]];now -= nw[q[head]];head++;while (r <= tail && now + nw[q[r]] <= s) {now += nw[q[r]];dr -= nw[q[r]];r++;}}cout << max(ans, tmp) << '\n';return 0;
}