SDOI2011的Dayx第2题
题意：
在树中找到一条权值和不超过S的链（为什么是链呢，因为题目中提到“使得路径的两端都是城市”，如果不是链那不就不止两端了吗——怎么这么机智的感觉...），使得不在链上的点与这条链的距离最大值最小。
SOL：
最大值最小！这不是二分的节奏么？然而hzw学长说二分更直观我却一点都没有体会到...
这道题的关键是猜想（貌似还挺好想）并证明（貌似一直都是可有可无的东西，不过还挺好证的），路径一定在直径上，那么我们先两遍*FS找到直径，用一个队列维护链上的路径，以及预处理出直径上的点其子树中距离最远的点的距离，再维护路径两头距离直径的两端的距离即可，答案即这三者的最大值。
总感觉应该挺快的吧但是居然比他们二分答案的慢了几倍（A得窝囊），我也就是用了一个set而已（方便取出与删除然而我觉得可以再优化不用这个set...
关于证明：（自己口胡的证明，极其不严谨
证明还是非常好证的（也就自己yy），我们假设一条直径，假设最优的链不在这条直径上——我们可以把这条链看作一个点，那么可以证明它的最远点一定是直径的两个端点之一（否则树的直径就可以更长），那么显然这条链是包含直径的一部分的，再证全部包含，只要在部分包含的基础上对延伸进行讨论，就得证了吧...（感觉对了就好了不过是给自己a掉多找一个正当理由...）
CODE：
代码实现不是很难，然而我RE几次方了把DFS改成BFS又把自带queue改成手工队列——结果小细节错误百出...
/*==========================================================================
# Last modified: 2016-02-12
# Filename: 2016trainning1 t1.cpp
# Description:
==========================================================================*/
#define me AcrossTheSky
#include <cstdio>
#include <cmath>
#include <ctime>
#include <string>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm> #include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define lowbit(x) (x)&(-x)
#define INF 1000000000
#define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++)
#define FORP(i,a,b) for(int i=(a);i<=(b);i++)
#define FORM(i,a,b) for(int i=(a);i>=(b);i--)
#define ls(a,b) (((a)+(b)) << 1)
#define rs(a,b) (((a)+(b)) >> 1)
#define check(ch) (ch>='0'&&ch<='9')
#define maxn 300001
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int ans=INF;
void read(int &t){
int ch;
for(ch=getchar( );!check(ch);ch=getchar( ));
t=ch-'';
for(ch=getchar( );check(ch);ch=getchar( ))t*=,t+=ch-'';
}
/*==================split line==================*/
int n,s,sume=,maxx;
struct Edge{
int to,len;
}e[maxn*];
struct cmp{
bool operator()(const int &x,const int &y) const{
return x>y;
}
};
int first[maxn],next[maxn*],nextn[maxn],dis[maxn],temp[],f[maxn],pre[maxn];
int q[maxn*];
bool vis[maxn];
set<int,cmp> b;
void addedge(int x,int y,int len){
sume++; e[sume].to=y; e[sume].len=len;
next[sume]=first[x]; first[x]=sume;
}
void bfs(int node,int d){
memset(q,,sizeof(q));
int front=,tail=; dis[node]=;
q[front]=node; vis[node]=true;
while (front<=tail){
int x=q[front];
front++;
if (dis[x]>maxx) maxx=dis[x],temp[d]=x;
for (int i=first[x];i!=-;i=next[i])
if (!vis[e[i].to]){
pre[e[i].to]=x;
dis[e[i].to]=dis[x]+e[i].len;
tail++; q[tail]=e[i].to; vis[e[i].to]=true;
}
}
}
void bfs1(int node,int root){
memset(q,,sizeof(q));
int front=,tail=; q[front]=node;
while (front<=tail){
int x=q[front]; front++; vis[x]=true;
f[root]=max(f[root],dis[x]-dis[root]);
for (int i=first[x];i!=-;i=next[i])
if (e[i].to!=nextn[node] && !vis[e[i].to]){
tail++; q[tail]=e[i].to;
}
}
}
int main(){
read(n); read(s);
FORP(i,,n) first[i]=-;
FORP(i,,n-) {
int x,y,l;
read(x); read(y); read(l);
addedge(x,y,l); addedge(y,x,l);
}
maxx=; bfs(,);
memset(vis,false,sizeof(vis));
maxx=; bfs(temp[],);
int L=temp[],R=temp[];
memset(vis,false,sizeof(vis));
for (int i=L;i!=R;i=pre[i]) nextn[pre[i]]=i;
L=temp[],R=temp[];
for (int i=L;i!=R;i=nextn[i]) { vis[i]=true; bfs1(i,i); }
vis[R]=true; bfs1(R,R);
int llen=,rlen=maxx,head=L,tail=L,len=; while (true){
if (head==R) break;
if (dis[nextn[head]]<s) {
len=dis[nextn[head]];
head=nextn[head];
b.insert(f[head]);
rlen=maxx-dis[head];
continue;
}
break;
} int t=max(rlen,max(llen,*b.begin()));
if (t<ans) ans=t;
while (head!=R){
len=dis[nextn[head]];
head=nextn[head];
rlen=maxx-dis[head];
while(len-dis[tail]>s){
b.erase(f[tail]); tail=nextn[tail]; llen=dis[tail];
}
t=max(rlen,max(llen,*b.begin()));
if (t<ans) ans=t;
}
printf("%d",ans);
}