应该不算评论区题解罢？

rt，这题本人照着[BJOI2017]树的难题的思路敲了暴力的单调队列按秩合并的程序，但没有按照题解中“01分数规划”的思想在外面套一个二分。

我采取的方式是在单调队列尾只要发现新加入答案更优，就弹掉队尾；在队首先弹完不合法的，然后只要排第二的答案更优就弹掉队首。

代码长这样：

while(tmp>=0&&tmp+dep[x]>=L){
	while(!dq.empty()&&(buc[tmp]+sum[x])*(dq.back()+dep[x])>=(buc[dq.back()]+sum[x])*(tmp+dep[x]))dq.pop_back();
	dq.push_back(tmp--);
}
while(!dq.empty()&&dq.front()+dep[x]>R)dq.pop_front();
while(dq.size()>=2&&(buc[dq[0]]+sum[x])*(dq[1]+dep[x])<=(buc[dq[1]]+sum[x])*(dq[0]+dep[x]))dq.pop_front();
if(!dq.empty())mx=max(mx,1.0*(buc[dq.front()]+sum[x])/(dq.front()+dep[x]));

我感觉这是错的，但是又不知道怎么证伪；况且此代码也能够AC。所以求助各位神仙，可以hack的，给出一组数据；如果能够证明正确性，那么这题就多了种$n\log n$的做法。

完整代码：

#pragma GCC optimize(3)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
const ll fni=-1e11;
int n,L,R;
double mx;
int ROOT,SZ,sz[200100],msz[200100];
int dep[200100],mdp[200100],lim;
ll sum[200100],buc[200100];
vector<pair<int,int> >v[200100];
bool vis[200100];
void getsz(int x,int fa){
	sz[x]=1;
	for(auto i:v[x])if(!vis[i.first]&&i.first!=fa)getsz(i.first,x),sz[x]+=sz[i.first];
}
void getroot(int x,int fa){
	sz[x]=1,msz[x]=0;
	for(auto i:v[x])if(!vis[i.first]&&i.first!=fa)getroot(i.first,x),sz[x]+=sz[i.first],msz[x]=max(msz[x],sz[i.first]);
	msz[x]=max(msz[x],SZ-sz[x]);
	if(msz[x]<msz[ROOT])ROOT=x;
}
void getdep(int x,int fa,int fr){
	mdp[fr]=max(mdp[fr],dep[x]);
	for(auto i:v[x])if(!vis[i.first]&&i.first!=fa)dep[i.first]=dep[x]+1,sum[i.first]=sum[x]+i.second,getdep(i.first,x,fr);
}
bool cmp(pair<int,int>x,pair<int,int>y){
	return mdp[x.first]<mdp[y.first];
}
queue<int>q;
deque<int>dq;
void bfsread(int x){
	dq.clear();
	q.push(x);
	int tmp=lim;
	while(!q.empty()){
		x=q.front(),q.pop();
		while(tmp>=0&&tmp+dep[x]>=L){
			while(!dq.empty()&&(buc[tmp]+sum[x])*(dq.back()+dep[x])>=(buc[dq.back()]+sum[x])*(tmp+dep[x]))dq.pop_back();
			dq.push_back(tmp--);
		}
		while(!dq.empty()&&dq.front()+dep[x]>R)dq.pop_front();
		while(dq.size()>=2&&(buc[dq[0]]+sum[x])*(dq[1]+dep[x])<=(buc[dq[1]]+sum[x])*(dq[0]+dep[x]))dq.pop_front();
		if(!dq.empty())mx=max(mx,1.0*(buc[dq.front()]+sum[x])/(dq.front()+dep[x]));
		for(auto i:v[x])if(!vis[i.first]&&dep[i.first]>dep[x])q.push(i.first);
	}
}
void bfswrite(int x){
	q.push(x);
	while(!q.empty()){
		x=q.front(),q.pop();
		buc[dep[x]]=max(buc[dep[x]],sum[x]),lim=max(lim,dep[x]);
		for(auto i:v[x])if(!vis[i.first]&&dep[i.first]>dep[x])q.push(i.first);
	}
}
void calc(int x){
	sum[x]=dep[x]=0;
	for(auto i:v[x])if(!vis[i.first])sum[i.first]=i.second,dep[i.first]=1,getdep(i.first,x,i.first);
	sort(v[x].begin(),v[x].end(),cmp);
	for(auto i:v[x])if(!vis[i.first])mdp[i.first]=0,bfsread(i.first),bfswrite(i.first);
	for(int i=1;i<=lim;i++)buc[i]=fni;lim=0;
}
void solve(int x){
	calc(x);
	getsz(x,0); 
	vis[x]=true;
	for(auto i:v[x])if(!vis[i.first])ROOT=0,SZ=sz[i.first],getroot(i.first,0),solve(ROOT);
}
void read(int &x){
	x=0;
	char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
int main(){
	read(n),read(L),read(R);
	for(int i=1;i<=n;i++)buc[i]=fni;
	for(int i=1,x,y,z;i<n;i++)read(x),read(y),read(z),v[x].push_back(make_pair(y,z)),v[y].push_back(make_pair(x,z));
	msz[0]=n+1,SZ=n,getroot(1,0),solve(ROOT);
	printf("%.3lf\n",mx);
	return 0;
}