题目描述

Description

某个国家有n个城市，这n个城市中任意两个都连通且有唯一一条路径，每条连通两个城市的道路的长度为zi(zi<=1000)。
这个国家的人对火焰有超越宇宙的热情，所以这个国家最兴旺的行业是消防业。由于政府对国民的热情忍无可忍（大量的消防经费开销）可是却又无可奈何（总统竞选的国民支持率），所以只能想尽方法提高消防能力。
现在这个国家的经费足以在一条边长度和不超过s的路径（两端都是城市）上建立消防枢纽，为了尽量提高枢纽的利用率，要求其他所有城市到这条路径的距离的最大值最小。
你受命监管这个项目，你当然需要知道应该把枢纽建立在什么位置上。

Input

输入包含n行：
第1行，两个正整数n和s，中间用一个空格隔开。其中n为城市的个数，s为路径长度的上界。设结点编号以此为1，2，……，n。
从第2行到第n行，每行给出3个用空格隔开的正整数，依次表示每一条边的两个端点编号和长度。例如，“2 4 7”表示连接结点2与4的边的长度为7。

Output

输出包含一个非负整数，即所有城市到选择的路径的最大值，当然这个最大值必须是所有方案中最小的。

Sample Input

【样例输入1】

5 2
1 2 5
2 3 2
2 4 4
2 5 3

【样例输入2】

8 6
1 3 2
2 3 2
3 4 6
4 5 3
4 6 4
4 7 2
7 8 3

Sample Output

【样例输出1】

5

【样例输出2】

5

HINT

对于100%的数据，n<=300000，边长小等于1000。

题目分析：

这道题是NOIP《树网的核》
至于为什么路径一定在直径上 我不会证......
我们先把任意一条直径拿下来 然后要用到这些数组：
d[x]:点x不经过直径上的边  到它子树里的点的最大值
fir[x]:从直径左端点到x点的直径边权前缀和
las[x]:从直径右端点到x点的直径边权后缀和
令一段区间[l,r]为我们的路径
所以 所有点到这条路径的最大距离就是
max{max(fir[l],las[r]),max(d[j]),(l<=j<=r)}
同时要保证从l到r的路径长度下<=s
所以 果断双指针+线段树啊

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n;
long long m;
int head[500100],to[500010*2],net[500010*2];
long long val[500010*2];
int tot;
void add(int x,int y,long long c)
{
	net[++tot]=head[x];
	to[tot]=y;
	val[tot]=c;
	head[x]=tot;
}
long long dis[500010];
int fa[500010];
int bfs(int x)
{
	memset(fa,0,sizeof fa);
	for(int i=1;i<=n;i++) dis[i]=10000000000000; 
	queue<int>q;
	q.push(x);
	dis[x]=0;
	while(q.size())
	{
		int nmp=q.front();q.pop();
		for(int i=head[nmp];i;i=net[i])
			if(to[i]!=fa[nmp])
			{
				fa[to[i]]=nmp;
				dis[to[i]]=dis[nmp]+val[i];
				q.push(to[i]);
			}
	}
	int temp=x;
	for(int i=1;i<=n;i++) if(dis[temp]<dis[i]) temp=i;
	return temp;
}
int a[501000];
long long value[501000];
int vis[501000];
long long d[501000];
long long dfs(int x,int temp,long long c)
{
	long long nmp=c;
	for(int i=head[x];i;i=net[i])
		if(to[i]!=temp&&!vis[to[i]])
			nmp=max(nmp,dfs(to[i],x,c+val[i]));
	return nmp;
}
long long fir[501000],las[501000]; 
long long ans=100000000000,all;
struct your
{
	int x,y;
	long long maxx;
}b[3000000];
void build(int dx,int dy,int num)
{
	b[num].x=dx,b[num].y=dy;
	if(dx==dy)
	{
		b[num].maxx=d[dx];
		return ;
	}
	int mid=(dx+dy)>>1;
	build(dx,mid,num<<1);
	build(mid+1,dy,num<<1|1);
	b[num].maxx=max(b[num<<1].maxx,b[num<<1|1].maxx);
}
long long ask(int dx,int dy,int num)
{
	if(dx==b[num].x&&dy==b[num].y) return b[num].maxx;
	int mid=(b[num].x+b[num].y)>>1;
	if(dx>mid) return ask(dx,dy,num<<1|1);
	if(dy<=mid) return ask(dx,dy,num<<1);
	return max(ask(dx,mid,num<<1),ask(mid+1,dy,num<<1|1));
}
int main()
{
	scanf("%d%lld",&n,&m);
	for(int i=1;i<n;i++)
	{
		int x,y;
		long long c;
		scanf("%d%d%lld",&x,&y,&c);
		add(x,y,c),add(y,x,c);
	}
	int tmp,nmp,temp;
	tmp=bfs(1); 
	nmp=bfs(tmp); 
	temp=nmp;
    while(temp!=tmp)
    	vis[temp]=1,a[++a[0]]=temp,temp=fa[temp];
    a[++a[0]]=temp,vis[temp]=1;
   	for(int i=1;i<a[0];i++)
   		for(int j=head[a[i]];j;j=net[j])
   			if(to[j]==a[i+1])
   			{
   				value[i+1]=val[j];
   				break;
   			}
   	for(int i=1;i<=a[0];i++) d[i]=dfs(a[i],0,0);
   	for(int i=1;i<=a[0];i++) fir[i]=max(fir[i-1]+value[i],d[i]);
   	for(int i=a[0];i>=1;i--) las[i]=max(las[i+1]+value[i+1],d[i]);
   	int l=1,r=0;
   	temp=0;
   	build(1,a[0],1);
  	for(int i=1;i<=a[0];i++)
  	{	
  		temp+=value[i];
  		if(temp>m)
  			while(l<i&&temp>m) temp-=value[++l];
  		all=max(ask(l,i,1),max(fir[l],las[i]));
  		ans=min(ans,all);
  	}
  	printf("%lld",ans);
        return 0 ;
}