路过的大佬帮忙看看，代码有点答辩，但是应该是容易看懂的。

悬赏 2 关。

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
const double eps=1e-4;
int n;
int wson[N],len[N];
double t[N<<2],ans[N],buf[N];
double *f[N],*p=buf;
double mns;
struct edge{
	int to,w;
};
vector<edge> e[N];
void update(int x,int l,int r,int pos,double k){
	if(l==r){
		t[x]=k;
		return;
	}
	int mid=(l+r)>>1;
	if(pos<=mid)update(x<<1,l,mid,pos,k);
	else update(x<<1|1,mid+1,r,pos,k);
	t[x]=max(t[x<<1],t[x<<1|1]);
}
double query(int x,int l,int r,int L,int R){
	if(L<=l&&r<=R)return t[x];
	int mid=(l+r)>>1;
	double res=0;
	if(L<=mid)res=max(res,query(x<<1,l,mid,L,R));
	if(R>mid)res=max(res,query(x<<1|1,mid+1,r,L,R));
	return res;
}
int L,U;
double up[N];
void dfs1(int x,int fa){
	for(auto to:e[x]){
		int y=to.to;double w=to.w-mns;
		if(y==fa)continue;
		up[y]=w;
		dfs1(y,x);
		if(len[y]>len[wson[x]])wson[x]=y;
	}
	len[x]=len[wson[x]]+1;
}
void dfs2(int x,int fa){
	if(wson[x]){
		f[wson[x]]=f[x]+1;
		dfs2(wson[x],x);
		for(int j=1;j<len[x];++j){
			f[x][j]+=up[wson[x]];
			if(j>=L&&j<=U)ans[x]=max(ans[x],f[x][j]);
		}
			
		ans[x]=max(ans[x],ans[wson[x]]);
	}
	for(auto to:e[x]){
		int y=to.to;double w=to.w-mns;
		if(y==fa||y==wson[x])continue;
		f[y]=p,p+=len[y];
		dfs2(y,x);
		ans[x]=max(ans[x],ans[y]);
		for(int j=0;j<len[x];++j){
			int S=f[y]-buf+max(0,min(len[y]-1,L-j-1)),T=f[y]-buf+min(len[y]-1,max(U-j-1,0));
			if(j+len[y]>=L&&j<=U)ans[x]=max(ans[x],f[x][j]+w+query(1,0,n,S,T));
			if(j&&w+f[y][j-1]>f[x][j])
				f[x][j]=w+f[y][j-1];
		}
	}
	for(int j=0;j<len[x];++j)
		update(1,0,n,f[x]-buf+j,f[x][j]);
}
bool check(){
	for(int i=1;i<=n;++i)ans[i]=-1e9,buf[i]=0;
	for(int i=1;i<=(N<<1);++i)t[i]=0;
	dfs1(1,0);
	p=buf;
	f[1]=p,p+=len[1];
	dfs2(1,0);
	
	if(ans[1]>=0)return 1;
	return 0;
}
int main(){
	cin>>n>>L>>U;
	for(int i=1;i<n;++i){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		e[u].push_back({v,w});
		e[v].push_back({u,w});
	}
	double l=0,r=1000000;
	while(r-l>=eps){
//		cout<<l<<" "<<r<<"\n";
		mns=(l+r)/2;
		if(check())l=mns;
		else r=mns;
	}
	printf("%.3lf",mns);
	
}