[lg2491][SDOI2011]消防

题目大意:

给定n个点的带边权树,找出一条长度不超过s的链,使节点到链的最大距离最小,求最大距离最小值。


思路

首先,显然所求路径在直径上。

证明

假设所求路径不在直径上,显然距最远的点上。
则设两端点为,路径上,端点为

上有点向外延伸出路径,上有点使路径(设为)使得
均为可行方案,但,故方案更优。证毕。

所以我们先bfs求出整条直径,
然后维护 g[i]表示i是路径右端点时,右边那段删掉的直径长度。
f[i]表示i是路径左端点时,左边那段删掉的直径长度。
h[i]表示i是直径上的点时,以i为根不在直径上的子树中离i的最大距离。
从左到右枚举左端点,然后右端点是非严格单调右移的。
而对于一段路径区间[l,r],它作为枢纽时的答案为

h[i]用单调队列维护。


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
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
#include <cstdio>
#include <cctype>
#include <cstring>
#include <queue>
#include <algorithm>
#define N 300010
#define inf 100000000
int head[N],next[N << 1],to[N << 1],tot = 0,val[N << 1];
int id[N],f[N],g[N],fa[N],vis[N],que[N],tmp[N],bel[N],h[N];
int n,s,k,t,num,L,R;
inline int getint()
{
register int num = 0,sgn = 1;register char ch = getchar();for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = 0;
for(;isdigit(ch);ch = getchar()) num = (num << 3) + (num << 1) + ch - '0';return sgn ? num : -num;
}
inline void addedge(int u,int v,int w)
{
next[++tot] = head[u];to[tot] = v;val[tot] = w;head[u] = tot;
next[++tot] = head[v];to[tot] = u;val[tot] = w;head[v] = tot;
}
inline void init()
{
memset(head,-1,sizeof(head));
}
std::queue<int> q;
int bfs(int s,int time)
{
int len = 0;q.push(s);
g[s] = 0;fa[s] = s;vis[s] = time;
while(!q.empty())
{
int u = q.front();q.pop();
for(int i = head[u],v = to[i];~i;v = to[(i = next[i])])
{
if(vis[v] == time) continue;
g[v] = g[u] + val[i];len = std::max(len,g[v]);
fa[v] = u;vis[v] = time;
q.push(v);
}
}
return len;
}
void solve()
{
int s,i;for(bfs(s = 1,++num),i = 1;i <= n;i++) if(g[i] > g[s]) s = i;
for(bfs(s,++num),i = 1;i <= n;i++) if(g[i] > g[t]) t = i;
bel[n = 1] = t;num++;
do
{
t = fa[t],bel[++n] = t;vis[t] = num;
}while(t != s);
for(i = 1;i <= n;i++) f[i] = g[bel[1]] - g[bel[i]];
for(i = 1;i <= n;i++) tmp[i] = g[bel[i]];
for(i = 1;i <= n;i++) h[i] = bfs(bel[i],num);
for(i = 1;i < n;i++) g[i] = tmp[i];
g[n] = 0;
}
int main()
{
init();
n = getint();s = getint();
for(int i = 1,x,y,z;i < n;i++)
{
x = getint();y = getint();z = getint();
addedge(x,y,z);
}
solve();
int ans = inf;
for(int l = 1,r = 0;l <= n;l++)
{
while(r < n && f[r + 1] - f[l] <= s)
{
++r;while(L <= R && que[R] < h[r]) R--;
que[++R] = h[r];id[R] = r;
}
ans = std::min(ans,std::max(std::max(f[l],g[r]),que[L]));
if(id[L] <= l) L++;
}
printf("%d\n",ans);
return 0;
}