「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;
}