「SOL」重建計劃(BZOJ)

/*Lucky_Glass*/
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

inline int rin(int &r){
	int b=1,c=getchar();r=0;
	while(c<'0' || '9'<c) b=c=='-'?-1:b,c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
	return r*=b;
}
const int N=1e5+10;
#define con(type) const type &
const double EPS=1e-8;
typedef pair<int,int> pii;

struct SuperDeque{
	int ary[N],le,ri;
	void clear(){le=1,ri=0;}
	void push_back(con(int)x){ary[++ri]=x;}
	void pop_back(){ri--;}
	void pop_front(){le++;}
	int back(){return ary[ri];}
	int front(){return ary[le];}
	int size(){return ri-le+1;}
}que;

int n,bonl,bonr,rsiz,rwei,rroot;
int siz[N],hgt[N];
double val_bas;
double val_bin[N],tmp_bin[N];
bool ban[N],ifsort[N];
vector<pii> lnk[N];

int findCenter(con(int)u,con(int)fa){
	int maxsizv=0,sizu=1;
	for(int it=0,itt=(int)lnk[u].size();it<itt;it++){
		int v=lnk[u][it].first;
		if(v==fa || ban[v]) continue;
		int sizv=findCenter(v,u);
		maxsizv=max(maxsizv,sizv);
		sizu+=sizv;
	}
	int weiu=max(rsiz-sizu,maxsizv);
	if(weiu<rwei) rwei=weiu,rroot=u;
	return sizu;
}
int dataDFS(con(int)u,con(int)fa,con(double)val,con(int)dep){
	int ret=0;
	siz[u]=1;
	tmp_bin[dep]=max(tmp_bin[dep],val);
	for(int it=0,itt=(int)lnk[u].size();it<itt;it++){
		int v=lnk[u][it].first;
		if(v==fa || ban[v]) continue;
		ret=max(ret,dataDFS(v,u,val+lnk[u][it].second-val_bas,dep+1));
		siz[u]+=siz[v];
	}
	return ret+1;
}
int highDFS(con(int)u,con(int)fa){
	int ret=0;
	for(int it=0,itt=(int)lnk[u].size();it<itt;it++){
		int v=lnk[u][it].first;
		if(v==fa || ban[v]) continue;
		ret=max(ret,highDFS(v,u));
	}
	return ret+1;
}
bool cmp(con(pii)a,con(pii)b){return hgt[a.first]<hgt[b.first];}
bool ina_abs(con(double)key){return key<0?-key:key;}
int sgn(con(double)key){return ina_abs(key)<EPS?0:(key<0?-1:1);}
bool dacDFS(int u,con(int)totsiz){
	ban[u]=true;
	if(!ifsort[u]){
		for(int it=0,itt=(int)lnk[u].size();it<itt;it++){
			int v=lnk[u][it].first;
			if(ban[v]) continue;
			hgt[v]=highDFS(v,u);
		}
		sort(lnk[u].begin(),lnk[u].end(),cmp);
		ifsort[u]=true;
	}
	fill(val_bin,val_bin+totsiz+1,-1e9),val_bin[0]=0;
	int ardlen=0;
	for(int it=0,itt=(int)lnk[u].size();it<itt;it++){
		int v=lnk[u][it].first;
		if(ban[v]) continue;
		int hgtv=dataDFS(v,0,lnk[u][it].second-val_bas,1);
		que.clear();
		for(int i=1,j=ardlen;i<=hgtv;i++){
			while(j>=bonl-i && j>=0){
				while(que.size() && sgn(val_bin[que.back()]-val_bin[j])<=0)
					que.pop_back();
				que.push_back(j);
				j--;
			}
			while(que.size() && que.front()>bonr-i) que.pop_front();
			if(que.size() && sgn(val_bin[que.front()]+tmp_bin[i])>=0)
				return true;
		}
		for(int i=1;i<=hgtv;i++){
			val_bin[i]=max(val_bin[i],tmp_bin[i]);
			tmp_bin[i]=-1e9;
		}
		ardlen=hgtv;
	}
	for(int it=0,itt=(int)lnk[u].size();it<itt;it++){
		int v=lnk[u][it].first;
		if(ban[v]) continue;
		rwei=1e9,rsiz=siz[v];
		findCenter(v,0);
		if(dacDFS(rroot,siz[v])) return true;
	}
	return false;
}
bool check(con(double)mmi){
	fill(tmp_bin,tmp_bin+1+n,-1e9);
	for(int i=1;i<=n;i++) ban[i]=false;
	val_bas=mmi;
	rsiz=n,rwei=1e9,findCenter(1,0);
	return dacDFS(rroot,n);
}
int main(){
	rin(n),rin(bonl),rin(bonr);
	for(int i=1,u,v,l;i<n;i++){
		rin(u),rin(v),rin(l);
		lnk[u].emplace_back(v,l);
		lnk[v].emplace_back(u,l);
	}
	double lle=0,rri=1e6,mmi;
	while(lle+1e-4<rri){
		mmi=(lle+rri)/2;
		if(check(mmi)) lle=val_bas;
		else rri=val_bas;
	}
	printf("%.3f\n",lle);
	return 0;
}