原题链接 Luogu
题面描述
找出直径上一条不长于 \(s\) 的路径，使得到这条路径的最远点最近，求这个最近的最远距离。
解题思路
根据SDOI2013里的结论，我们知道，所有的直径组成了中间的重合部分和两边的分叉部分。
思考一下就会发现，选取位于分叉部分的点是没有任何意义的。因为对于一个分叉点，至少有两个不同直径的端点贡献了到它的最远距离。无论接下来选择哪一条直径，另一条直径的端点到路径的距离都不会缩短，不可能使答案更小。
所以像SDOI2013题解里说的一样，我们先找出重合部分，然后在重合部分上暴力枚举+搜索判断，即可 AC。
AC 代码
code
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
| #include <bits/stdc++.h>
using namespace std;
#define FILE_IO
namespace io {...};
using namespace io;
const int maxn = 2e5 + 5;
int main() {
u = rr;
vector<int> he;
he.emplace_back(rr);
while (u != ll) {
u = f[u];
he.emplace_back(u);
}
int ans = 0x3f3f3f3f;
for (int i = 0; i < he.size(); i++) {
for (int j = i; j < he.size(); j++) {
if (abs(dis[he[j]] - dis[he[i]]) > s) continue;
memset(book, 0, sizeof book);
for (int k = i; k <= j; k++) book[he[k]] = true;
int tmp = 0;
for (int k = i; k <= j; k++) tmp = max(tmp, dfs3(he[k]));
ans = min(ans, tmp);
}
}
write(ans);
return 0;
}
|