题解 P2491 【[SDOI2011]消防】
/* %20的数据是树网的核，直接O(n^3)，怎么暴力怎么打。
%50的话，我也不知道怎么搞，能想出50，正解应该就很容易想到了。
然后正解的话我们可以想到，需要选的路径的所有边都在直径上是最优的。
因为离树上任意一点最远的点一定是直径的端点，所以我们选择的路径要与直径相交上才会产生最优解，
至于为什么整条路径都在直径上最优，
我们不妨假设现在有一棵树，
将直径上的一个点作为我们要选的路径上的一点，
我们要以这个点为中心扩展出一条路径，
离这个点最远的点一定是直径的端点，当前的最大值就是这个长度。
这时如果我们选的一条边不在直径上，并不会更新这个最大值，
这样即使不能继续在直径上延长，也对答案没有贡献，
于是为了方便处理，我们将整条路径都放在直径上，
但是这些不在直径上的路径的长度不能忽略，需要进行处理，
想通了这些，这道题就很简单了。
首先我们先用两遍bfs求出直径的两个端点，再把整条直径找出来，时间复杂度O(N)
然后对于每个直径上的点我们做一次dfs，求出不经过直径的以这个点源的路径的最大长度，一起取一个最大值，作为答案的最小值，这个步骤看上去是O(N^2)，而实际上我们对于整棵树上的每一个点只会跑一次，于是时间复杂度为O(N)。
最后我们再以之前求得的最大值为左端点，直径的长度为右端点，二分答案，就可以很轻松的得出结果了。
下面是代码，写的有点丑
*/
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+20;
int a[N],to[N*2],nex[N*2],w[N*2],b[N],c[N];
int ll,rr,l,r;
int bfs(int x)
{
memset(c,0,sizeof(c));//两遍bfs求出直径的两个端点
b[1]=x;
int head=0,tail=1;
int ans,s=0;
while(head!=tail)
{
head++;
for(int i=a[b[head]];i;i=nex[i])
{
if(!c[to[i]]&&to[i]!=x)
{
int y=to[i];
tail++;
c[y]=c[b[head]]+w[i];
b[tail]=y;
if(c[y]>s)
{
s=c[y];
ans=y;
}
}
}
}
return ans;
}
void dfs(int s1,int s2,int x,int t)//对于每个直径上的点dfs一次，求不经过直径的路径最大长度
{
l=max(l,t);
for(int i=a[x];i;i=nex[i])
{
if(to[i]!=s1&&to[i]!=s2)
{
dfs(x,x,to[i],t+w[i]);
}
}
}
void _dfs(int fa,int x,int y,int t,int s)//找出直径并对直径路径长度维护一个前缀和，方便以后处理。
{
if(x==y)
{
b[0]=t;
b[t]=s;
r=s;
return;
}
for(int i=a[x];i;i=nex[i])
{
if(fa!=to[i])
{
_dfs(x,to[i],y,t+1,s+w[i]);
if(b[0])
{
b[t]=s;
dfs(fa,to[i],x,0);
return;
}
}
}
}
bool pd(int t,int s)//判断答案是否可行。因为答案的左端点就是不经过直径的最大路径长，所以只需再直径上验证即可。
{
int i,j;
for(i=1;i<=b[0];++i)
{
if(b[i]>t)
break;
}
i--;
for(j=i;j<=b[0];++j)
{
if(b[j]-b[i]>s)
break;
}
j--;
return b[b[0]]-b[j]<=t;
}
int main()
{
int n,s;
scanf("%d%d",&n,&s);
for(int i=1,t=0;i<n;++i)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);//存边
nex[++t]=a[x];
to[t]=y;
w[t]=z;
a[x]=t;
nex[++t]=a[y];
to[t]=x;
w[t]=z;
a[y]=t;
}
ll=bfs(1);
rr=bfs(ll);
_dfs(0,ll,rr,1,0);
while(l!=r)//二分答案
{
int mid=(l+r)>>1;
if(pd(mid,s))r=mid;
else l=mid+1;
}
cout<<l;
return 0;
}