无脑上二分+淀粉质完事了

每个子树算的时候把儿子按照最长路径从小到大依次做,和前面的单调队列算一波,每个儿子的复杂度不超过这个子树大小

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define il inline
#define vd void
typedef long long ll;
il int gi(){
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=getchar();
}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
int n,L,R;
int fir[100010],dis[200010],nxt[200010],w[200010],id;
il vd link(int a,int b,int c){nxt[++id]=fir[a],fir[a]=id,dis[id]=b,w[id]=c;}
std::vector<std::pair<int,int> >G[100010];std::vector<int>Rt[100010];
int RT;
namespace build{
bool vis[100010];
int siz[100010],f[100010],N,rt;
il vd getrt(int x,int fa=-1){
siz[x]=1;f[x]=0;
for(int i=fir[x];i;i=nxt[i]){
if(dis[i]==fa||vis[dis[i]])continue;
getrt(dis[i],x);
siz[x]+=siz[dis[i]];
f[x]=std::max(f[x],siz[dis[i]]);
}
f[x]=std::max(f[x],N-siz[x]);
if(f[x]<f[rt])rt=x;
}
int maxl[100010];il bool cmp(const std::pair<int,int>&a,const std::pair<int,int>&b){return maxl[a.first]<maxl[b.first];}
il vd dfs(int x,int fa=-1){
maxl[x]=0;
for(int i=fir[x];i;i=nxt[i]){
if(dis[i]==fa||vis[dis[i]])continue;
dfs(dis[i],x);
maxl[x]=std::max(maxl[x],maxl[dis[i]]+1);
}
}
il vd build(int x){
vis[x]=1;
for(int i=fir[x];i;i=nxt[i])if(!vis[dis[i]])G[x].push_back(std::make_pair(dis[i],w[i]));
dfs(x);
std::sort(G[x].begin(),G[x].end(),cmp);
for(int i=0;i<G[x].size();++i){
rt=0;N=siz[G[x][i].first];getrt(G[x][i].first);
Rt[x].push_back(rt);build(rt);
}
}
il vd build(){
rt=0;f[0]=1e9;N=n;getrt(1);
RT=rt;build(rt);
}
}
double mid,res;
namespace dfz{
bool vis[100010];
double f[100010],g[100010];
int que[100010],hd,tl;
int N;
bool flg;
il vd dfs(int x,int fa=-1,int len=0,double sum=0){
if(N<len)g[N=len]=sum;
else g[len]=std::max(g[len],sum);
for(int i=fir[x];i;i=nxt[i]){
if(dis[i]==fa||vis[dis[i]])continue;
dfs(dis[i],x,len+1,sum+w[i]-mid);
}
}
il vd divide(int x){
vis[x]=1;int n=0;f[0]=0;
for(int i=0;i<G[x].size();++i){
N=0;g[0]=0;dfs(G[x][i].first,x,1,G[x][i].second-mid);
hd=tl=0;
for(int j=0,p=n;j<=N;++j){
while(~p&&p+j>=L){
while((hd^tl)&&f[que[tl-1]]<f[p])--tl;
que[tl++]=p--;
}
while((hd^tl)&&que[hd]+j>R)++hd;
if((hd^tl)&&f[que[hd]]+g[j]>0){flg=1;return;}
}
for(int i=0;i<=n;++i)f[i]=std::max(f[i],g[i]);
for(int i=n+1;i<=N;++i)f[i]=g[i];
n=N;
}
for(int i=0;i<Rt[x].size();++i){
divide(Rt[x][i]);
if(flg)return;
}
}
il vd clear(){flg=0;memset(vis,0,sizeof vis);}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
n=gi(),L=gi(),R=gi();
int a,b,c;for(int i=1;i<n;++i)a=gi(),b=gi(),c=gi(),link(a,b,c),link(b,a,c);
build::build();
double l=1,r=1000000;
while(r-l>1e-4){
mid=(l+r)*0.5;
dfz::clear();
dfz::divide(RT);
if(dfz::flg)l=mid;
else r=mid;
}
l=(l+r)*0.5;printf("%.3lf\n",l);
return 0;
}
05-04 07:29