「SDOI2011」消防

树的直径怎么求?拿出软尺,往树干上一绕,读出示数,再除以π就好了。

传送门

洛谷P2491

BZOJ2282

题解

首先,只要直径上存在一条小于$s$的边,那么答案中选择的路径必定在直径上。

所以只要将直径求出来,然后从将两个端点依次往里移动,直到当前路径的长度小于等于$s$时,此时的路径就是答案。

代码

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=300005,inf=0x3F3F3F3F;
int n,s,tot,lnk[maxn],son[maxn*2],nxt[maxn*2],w[maxn*2],rt,sum,u,v,Ver[maxn],E[maxn],Min[maxn],F[maxn],Max;bool flg,vis[maxn];
inline int read()
{
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
return ret*f;
}
inline void add_e(int x,int y,int z){tot++;son[tot]=y;w[tot]=z;nxt[tot]=lnk[x];lnk[x]=tot;}
void DFS(int now,int fa,int dist)
{
if(dist>sum){sum=dist;rt=now;}
for(int i=lnk[now];i;i=nxt[i])
if(son[i]!=fa)
DFS(son[i],now,dist+w[i]);
}
void DFS2(int now,int fa)
{
Ver[++Ver[0]]=now;vis[now]=true;
if(now==v){flg=true;return;}
for(int i=lnk[now];i&&!flg;i=nxt[i])
if(son[i]!=fa)
{E[++E[0]]=i;DFS2(son[i],now);if(!flg)E[0]--;}
if(!flg){Ver[0]--;vis[now]=false;}
}
void DFS3(int now,int fa,int rot,int dist)
{
for(int i=lnk[now];i;i=nxt[i])
{
if(son[i]!=fa&&!vis[son[i]])
{
DFS3(son[i],now,rot,dist+w[i]);
if(w[i]<=s&&dist<Min[rot]) Min[rot]=dist;
if(F[son[i]]+w[i]>F[now]) F[now]=F[son[i]]+w[i];
}
}
}
inline int Solve()
{
int L=1,R=Ver[0],D1=0,D2=0,ret=inf;
while(L<=Ver[0]&&R>=1)
{
if(L<R&&sum-D1-D2<=s) return max(Max,max(D1,D2));
if(L>=R)
{
if(max(D1,sum-D1)+Min[Ver[L]]<ret){ret=max(D1,sum-D1)+Min[Ver[L]];D1+=w[E[L]];L++;}
if(max(D2,sum-D2)+Min[Ver[R]]<ret){ret=max(D2,sum-D2)+Min[Ver[R]];D2+=w[E[R-1]];R--;}
}
if(D1+w[E[L]]<=D2+w[E[R-1]]){D1+=w[E[L]];L++;}
else{D2+=w[E[R-1]];R--;}
}
return ret;
}
int main()
{
n=read();s=read();
for(int i=1;i<n;i++)
{
int a=read(),b=read(),c=read();
add_e(a,b,c);add_e(b,a,c);
}
memset(Min,63,sizeof(Min));
DFS(1,0,0);u=rt;sum=0;
DFS(rt,0,0);v=rt;
DFS2(u,0);
for(int i=1;i<=Ver[0];i++)
{
DFS3(Ver[i],0,Ver[i],0);
if(F[Ver[i]]>Max) Max=F[Ver[i]];
}
printf("%d\n",Solve());
return 0;
}