今天晚上思维比较乱,以后再写写吧
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+,INF=1e9+;
double eps=1e-;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,L,U,a,b;
double w,maxVal,ans;
struct edge{
int v,ne;
double w;
}e[N<<];
int h[N],cnt;
inline void ins(int u,int v,double w){
cnt++;
e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;
cnt++;
e[cnt].v=u;e[cnt].w=w;e[cnt].ne=h[v];h[v]=cnt;
}
int f[N],size[N],all,vis[N],root;
void dfsRt(int u,int fa){
size[u]=;f[u]=;
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;
if(vis[v]||v==fa) continue;
dfsRt(v,u);
size[u]+=size[v];
f[u]=max(f[u],size[v]);
}
f[u]=max(f[u],all-size[u]);
if(f[u]<f[root]) root=u;
}
int q[N],head,tail,deep[N];
double val[N],mx[N];
bool visit[N];
void bfs(double g){
while(head<=tail){
int u=q[head++];
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;
if(vis[v]) continue;
if(!visit[v]){
visit[v]=;
q[++tail]=v;
deep[v]=deep[u]+;
val[v]=val[u]+e[i].w-g;
}
}
}
}
double c[N];
int m;
bool dp(int n){//printf("dp %d %d\n",n,n+m);
if(m+n<L) return false;
head=;tail=;
int l=max(L-n,),r=U-n;
for(int i=l;i<=r&&i<=m;i++){//printf("ins %d\n",i);
while(head<=tail&&c[q[tail]]<c[i]) tail--;
q[++tail]=i;
}
for(int i=n;i>=;i--){//printf("i %d %lf\n",i,mx[i]);
int l=L-i,r=U-i;//printf("lala %d %d\n",l,r);
while(head<=tail&&q[head]<l) head++;
while(head<=tail&&c[r]>c[q[tail]]) tail--;
q[++tail]=r;
//printf("qqq %d %d %lf\n",head,tail,c[q[head]]);
if(head<=tail&&c[q[head]]+mx[i]>=) return true;
}
return false;
}
bool check(int u,double g){//printf("\ncheck %d %lf\n",u,g);
for(int i=;i<=m;i++) c[i]=-INF;m=;
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;
if(vis[v]) continue;
//printf("\nv %d\n",v);
head=;tail=;
q[++tail]=v;
deep[v]=;val[v]=e[i].w-g;
bfs(g);
//for(int i=1;i<tail;i++) //printf("%lf ",val[i]);puts("");
for(int i=;i<=deep[q[tail]];i++) mx[i]=-INF;
int id;
for(int i=;i<=tail;i++)
id=q[i],mx[deep[id]]=max(mx[deep[id]],val[id]),visit[id]=;
//for(int i=1;i<=maxDeep;i++) printf("mx %d %lf \n",i,mx[i]);
if(dp(deep[q[tail]])) return true;
m=max(m,deep[q[tail]]);
for(int i=;i<=deep[q[tail]];i++) c[i]=max(c[i],mx[i]);
}
return false;
}
void dfsSol(int u){//printf("dfsSol %d\n",u);if(u!=1) return;
vis[u]=;
double l=ans,r=maxVal;//printf("lr %lf %lf\n\n",l,r);
while(r-l>eps){
double mid=(l+r)/;
if(check(u,mid)) l=mid;
else r=mid;
}
ans=max(ans,l);
for(int i=h[u];i;i=e[i].ne)
if(!vis[e[i].v]){
root=;all=size[e[i].v];
if(size[e[i].v]<L) continue;
dfsRt(e[i].v,);
dfsSol(root);
}
}
int main(){
freopen("in","r",stdin);
//freopen("out","w",stdout);
n=read();L=read();U=read();
for(int i=;i<n;i++)
a=read(),b=read(),w=read(),ins(a,b,w),maxVal=max(maxVal,w);
root=;f[]=INF;all=n;
dfsRt(,);
dfsSol(root);
printf("%.3lf",ans);
}