P2491 [SDOI2011] 消防

评测记录

#include<bits/stdc++.h>
#define N 300010
#define int long long
using namespace std;
int n,s;
int tot,hd[N],nex[2*N],to[2*N],val[2*N];
int ed,mn,dis[N],pre[N],lum[N],rum[N];
bool flg[N];
vector<int>dmr;
void add(int u,int v,int w)
{
	tot++;
	to[tot]=v;
	val[tot]=w;
	nex[tot]=hd[u];
	hd[u]=tot;
	return;
}
void findD(int u,int las)
{
	for(int i=hd[u];i!=0;i=nex[i])
	{
		int v=to[i],w=val[i];
		if(v==las) continue;
		dis[v]=dis[u]+w;
		pre[v]=u;
		if(dis[v]>dis[ed]) ed=v;
		findD(v,u);
	}
	return;
}
void dfs(int u,int las)
{
	for(int i=hd[u];i!=0;i=nex[i])
	{
		int v=to[i],w=val[i];
		if(v==las||flg[v]) continue;
		dis[v]=dis[u]+w;
		mn=max(mn,dis[v]);
		dfs(v,u);
	}
	return;
}
signed main()
{
	cin>>n>>s;
	int u,v,w;
	for(int i=1;i<=n-1;i++)
	{
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
	findD(1,0);
	dis[ed]=0;
	pre[ed]=0;
	findD(ed,0);
	int tmp=ed;
	lum[ed]=0;
	while(ed!=0)
	{
		lum[ed]=dis[tmp]-dis[ed];
		rum[ed]=dis[ed];
		flg[ed]=true;
		dmr.push_back(ed);
		if(pre[ed]==0) rum[ed]=0;
		ed=pre[ed];
	}
	memset(dis,0,sizeof dis);
	for(auto i:dmr)
	{
		mn=0;
		dis[i]=0;
		dfs(i,0);
		dis[i]=mn;
//		cout<<lum[i]<<" "<<rum[i]<<endl;
	}
	int l=0,r=0,sum=0;
	int ans=LONG_LONG_MAX;
	multiset<int>SSS;
	for(;r<dmr.size();r++)
	{
		sum=lum[dmr[r]]-lum[dmr[l]];
		SSS.insert(dis[r]);
		if(sum>s)
		{
			while(l<r&&sum>s)
			{
				SSS.erase(SSS.find(dis[l]));
				l++;
				sum=lum[dmr[r]]-lum[dmr[l]];
			}
		}
		ans=min(ans,max(*(--SSS.end()),max(lum[dmr[l]],rum[dmr[r]])));
	}
	cout<<ans;
	return 0;
}