aaa

zhang  •  3个月前


include

include

include

include

include

include

include

define RG register

define il inline

define iter iterator

define Max(a,b) ((a)>(b)?(a):(b))

define Min(a,b) ((a)<(b)?(a):(b))

using namespace std; const int N=200005,inf=2e8; const double eps=1e-5; typedef long long ll; inline int gi(){

RG char ch=getchar();RG int str=0;
while(ch>'9' || ch<'0')ch=getchar();
while(ch>='0' && ch<='9')str=(str<<1)+(str<<3)+ch-48,ch=getchar();
return str;

} int n,L,R,head[N],to[N<<1],nxt[N<<1],num=0,son[N]={N},sz[N]; int root=0,sum=0,rt[N],dep[N]; double dis[N<<1],sd[N<<1],p[N],d[N]; bool vis[N]; inline void link(int x,int y,int z){ nxt[++num]=head[x];to[num]=y;head[x]=num;dis[num]=sd[num]=z;} inline void getroot(int x,int last){ son[x]=0;sz[x]=1; for(int i=head[x];i;i=nxt[i]){ int u=to[i]; if(vis[u] || u==last)continue; getroot(u,x); sz[x]+=sz[u]; son[x]=Max(son[x],sz[u]); } son[x]=Max(son[x],sum-sz[x]); if(son[x]<son[root])root=x; } vectors[N]; int mx=0; inline void getdis(int x,int last){

mx=Max(dep[x],mx);
for(int i=head[x];i;i=nxt[i]){
	int u=to[i];
	if(vis[u] || u==last)continue;
	dep[u]=dep[x]+1;p[u]=p[x]+dis[i];
	if(dep[u]<=R)getdis(u,x);
}

} int q[N],pre[N],cnt=0,que[N],l=1,r=0; inline void bfs(int S,int last){

int x,u,t=0;cnt=1;
que[1]=S;pre[S]=last;
while(t!=cnt){
	x=que[++t];
	for(int i=head[x];i;i=nxt[i]){
		u=to[i];
		if(u==pre[x] || vis[u] || dep[u]>R)continue;
		pre[u]=x;que[++cnt]=u;
	}
}

for(int i=1;i<=cnt;i++)pre[que[i]]=0; } inline bool Clear(int maxdep){

for(int i=1;i<=maxdep;i++)d[i]=-inf,s[i].clear();

return true; } inline bool calc(int x){

int u,maxdep=0,v;
for(int i=head[x];i;i=nxt[i]){
	u=to[i];if(vis[u])continue;
	mx=0;dep[u]=1;p[u]=dis[i];
	getdis(u,x);
	if(mx>maxdep)maxdep=mx;
	s[mx].push_back(u);
}
for(int i=1;i<=maxdep;i++){
	int size=s[i].size();
	if(!size)continue;
	for(int j=0;j<size;j++){
		u=s[i][j];bfs(u,x);
		l=1;r=0;
		for(int k=i-1;k>=L-1;k--){
			while(l<=r && d[k]>=d[q[r]])r--;
			q[++r]=k;
		}
		for(int k=1;k<=cnt;k++){
			v=que[k];
			if(dep[v]>R)break;
			if(dep[v]>=L && p[v]>=0)return Clear(maxdep);

			while(l<=r && q[l]>R-dep[v])l++;
			if(L-dep[v]>=1){
				while(l<=r && d[L-dep[v]]>=d[q[r]])r--;
				q[++r]=L-dep[v];
			}
			if(d[q[l]]+p[v]>eps)return Clear(maxdep);
		}
		for(int k=1;k<=cnt;k++)
	   	d[dep[que[k]]]=Max(d[dep[que[k]]],p[que[k]]);
	}
}
Clear(maxdep);
return false;

} inline bool solve(int x){

vis[x]=1;
if(calc(x))return true;
for(int i=head[x];i;i=nxt[i]){
	if(vis[to[i]])continue;
	if(rt[i]){if(solve(rt[i]))return true;}
	else {
		sum=sz[to[i]];root=0;
		getroot(to[i],x);rt[i]=root;
		if(solve(rt[i]))return true;
	}
}
return false;

} int sroot=0; inline bool check(double mid){

for(int i=1;i<=num;i++)dis[i]=sd[i]-mid;
for(int i=0;i<=n;i++)vis[i]=0,d[i]=-inf;
return solve(sroot);

} void work() {

int x,y,z;
double l=0,r=0,mid,ans;
cin>>n>>L>>R;
for(int i=1;i<n;i++){
	x=gi();y=gi();z=gi();
	link(x,y,z);link(y,x,z);
	if(z>r)r=z;
}
sum=n;root=0;getroot(1,1);sroot=root;
while(l<=r-eps){
	mid=(l+r)/2;
	if(check(mid))ans=mid,l=mid+eps;
	else r=mid-eps;
}
printf("%.3lf\n",abs(ans));

}

int main() {

freopen("pp.in","r",stdin);
freopen("pp.out","w",stdout);
work();
return 0;

}


评论: