Codeforces 1004E(树的直径+单调队列滑动窗口)

Codeforces 1004E
题意:一棵$n$个点的树,你需要选出一条不超过$k$长度的链,使得其他所有点到链上的最短距离的最长距离最短。

这个有点像二分,但是并不好做。我们想到树的直径的性质,一棵树以直径中心为根子树深度最小。
考虑边权全是1的情况,选择的链一定在直径中间$k$长度的链。根据一棵树以直径中心为根子树深度最小性质很好证明。
现在有边权,那么就要找一个加权的直径,并且链也不在中间了。但是还在直径上。我们预处理出以下的信息:

$d1(u)$,直径上第$u$个点到左端点的距离
$d2(u)$,直径上第$u$个点的枝叶最长深度距离
$dl$,直径的带权长
$a(i)$,直径上的点从左到右的序号

求直径两遍 BFS,然后用 Dinic 分层图思想找出直径上的点。即找到一个任意点的最远点之后,找这个最远点的最远点时候顺便对于每个点分层,然后再从这个最远点往回一层一层地走必然能找到直径。对于$d1​$,顺便求出即可。$d2​$,DFS 求每个直径点往下枝叶最大深度即可,注意不要走到直径上。

然后对于最后的答案就化作:
$ans=min(max(d1(max(i - k + 1, 0)), dl - d1(i), d2(i), d2(i-1),……,d2(i-k+1)))$
对于后面的$d2$,就是一个滑动窗口最大值,用单调队列维护即可。

知识点:1 树上的这些最优化问题和直径、重心、二分、DP有关。
2 单调队列很容易写错,是检查重点
3 从简单到复杂,从极端到一般的思维方法很重要

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
const int MAXN = 100000 + 5;
struct edge {int nxt, v, wi;} ed[MAXN * 2];
int n, k, dl, que[MAXN * 2], l, r;
int en, hd[MAXN], dis[MAXN], vis[MAXN], a[MAXN], cnt, d2[MAXN], d1[MAXN];
std::queue<int > q;
std::queue<std::pair<int, int > > Q;
inline void ins(int x, int y, int w) {
ed[++en] = (edge){hd[x], y, w}, hd[x] = en;
ed[++en] = (edge){hd[y], x, w}, hd[y] = en;
}
void dfs(int u, int pa, int dep, int &sor) {
d2[sor] = std::max(d2[sor], dep);
for (int i = hd[u]; i > 0; i = ed[i].nxt) {
edge &e = ed[i];
if (e.v != pa && !vis[e.v]) dfs(e.v, u, dep + e.wi, sor);
}
}
void clean() {
en = 0, ms(hd, -1);
}
int solve() {
clean();
for (int u, v, d, i = 1; i < n; i++) scanf("%d%d%d", &u, &v, &d), ins(u, v, d);
ms(dis, 0), q.push(1);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = hd[u]; i > 0; i = ed[i].nxt) {
edge &e = ed[i];
if (!dis[e.v] && e.v != 1) dis[e.v] = dis[u] + e.wi, q.push(e.v);
}
}
int x = 1;
for (int i = 2; i <= n; i++) if (dis[i] > dis[x]) x = i;
ms(dis, 0), vis[x] = 1, Q.push(std::make_pair(x, 1));
while (!Q.empty()) {
std::pair<int, int > p = Q.front(); Q.pop();
int u = p.first, no = p.second;
for (int i = hd[u]; i > 0; i = ed[i].nxt) {
edge &e = ed[i];
if (!dis[e.v] && e.v != x) vis[e.v] = no + 1, dis[e.v] = dis[u] + e.wi, Q.push(std::make_pair(e.v, no + 1));
}
}
x = 1;
for (int i = 2; i <= n; i++) if (dis[i] > dis[x]) x = i;
dl = dis[x], k = std::min(k, vis[x]);
int rm = vis[x], now = x; a[++cnt] = x;
while (rm > 1) {
for (int i = hd[now]; i > 0; i = ed[i].nxt) {
edge &e = ed[i];
if (vis[e.v] == rm - 1) {
now = e.v, rm--, a[++cnt] = now, d1[cnt] = d1[cnt - 1] + e.wi;
break;
}
}
}
ms(vis, 0);
for (int i = 1; i <= cnt; i++) vis[a[i]] = 1;
for (int i = 1; i <= cnt; i++) dfs(a[i], 0, 0, i);
int ans = 1000000000, l = 1, r = 0;
for (int i = 1; i <= cnt; i++) {
while (l <= r && que[l] < i - k + 1) l++;
ans = std::min(ans, std::max(std::max(d2[que[l]], d1[std::max(i - k + 1, 0)]), dl - d1[i]));
while (l <= r && d2[i] >= d2[que[r]]) r--;
que[++r] = i;
}
printf("%d\n", ans);
return 0;
}
int main() {
scanf("%d%d", &n, &k), solve();
return 0;
}

------ 本文结束 ------