Description
solution
正解：分数规划+点分治
二分答案，把边的权值都改成 (dis-mid),然后做点分，看存不存在满足长度在([L,R]) (题目的要求)之间的路径，其边权和大于等于0.
考虑点分的维护，把当前root的子树分成已经处理完的集合 和 正在处理的集合.
显然存在一种线段树做法：我们把处理完的集合加入到以深度为下标的线段树中，每一次区间查询即可，查完之后再做单调修改，复杂度是 (O(n*log^3))
考虑怎么去掉这个线段树：
设当前处在深度为(i)的节点，我们发现每一次查询的是一个区间[L-i,R-i]，并且发现随着(i)增大，区间是在向右移动的，所以我们可以当做是在线段树维护的数组上做 窗口移动，单调队列维护即可.
代码还比较好写QAQ，注意题目卡常，需要记忆化点分的根
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#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;
}
vector<int>s[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
",abs(ans));
}
int main()
{
freopen("pp.in","r",stdin);
freopen("pp.out","w",stdout);
work();
return 0;
}