1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
| #include <cstdio>
#include <cstring>
#include <vector>
#include <utility>
#include <algorithm>
#define N 100005
typedef std::pair<int,int> P;
struct edge {int v;double w;} edges[N<<1];
int head[N],nxt[N<<1],idx=0;
inline void add(int u,int v,int w) {
edges[++idx]=(edge){v,w};nxt[idx]=head[u];head[u]=idx;
edges[++idx]=(edge){u,w};nxt[idx]=head[v];head[v]=idx;
}
int vis[N],tot[N],sum,rttot,rt;
void getrt(int x,int fa) {
tot[x]=1;int mxtot=0;
for(register int i=head[x];i;i=nxt[i]) {
edge &e=edges[i];if(e.v==fa||vis[e.v]) continue;
getrt(e.v,x);tot[x]+=tot[e.v];mxtot=std::max(mxtot,tot[e.v]);
}
mxtot=std::max(mxtot,sum-tot[x]);
if(mxtot<rttot) {rttot=mxtot;rt=x;}
}
int dep[N],mxdep;
void getmxdep(int x,int fa) {
mxdep=std::max(mxdep,dep[x]);
for(register int i=head[x];i;i=nxt[i]) {
edge &e=edges[i];if(e.v==fa||vis[e.v]) continue;
dep[e.v]=dep[x]+1;getmxdep(e.v,x);
}
}
P tmp[N];std::vector<int> es[N],rts[N];
void build(int x) {
vis[x]=true;int cnt=0;
for(register int i=head[x];i;i=nxt[i]) {
edge &e=edges[i];if(vis[e.v]) continue;
mxdep=0;dep[e.v]=1;getmxdep(e.v,x);tmp[cnt++]=P(mxdep,i);
}
std::sort(tmp,tmp+cnt);
for(register int i=0;i<cnt;++i) es[x].push_back(tmp[i].second);
for(register int i=0,end=es[x].size();i<end;++i) {
edge &e=edges[es[x][i]];if(vis[e.v]) continue;
sum=rttot=tot[e.v];getrt(e.v,0);rts[x].push_back(rt);build(rt);
}
}
struct type {int dep;double val;} cur[N];
double ans,val[N],box[N],h[N];int cnt=0;
void calc(int x,int fa) {
cur[cnt++]=(type){dep[x],val[x]};
for(register int i=head[x];i;i=nxt[i]) {
edge &e=edges[i];if(e.v==fa||vis[e.v]) continue;
dep[e.v]=dep[x]+1;val[e.v]=val[x]+e.w;calc(e.v,x);
}
}
int n,L,U,q[N];
bool solve(int x) {
vis[x]=true;int lstdep=h[0]=0;
for(register int i=0,end=es[x].size();i<end;++i) {
edge &e=edges[es[x][i]];if(vis[e.v]) continue;
cnt=mxdep=0;dep[e.v]=1;val[e.v]=e.w;calc(e.v,x);
for(register int j=0;j<cnt;++j) {
mxdep=std::max(mxdep,cur[j].dep);
box[cur[j].dep]=std::max(box[cur[j].dep],cur[j].val);
}
int head=1,tail=0,ls=L-mxdep,rs=U-mxdep;
for(register int j=std::max(ls,0);j<=std::min(rs,lstdep);++j) {
while(head<=tail&&h[q[tail]]<h[j]) --tail;q[++tail]=j;
}
if(head<=tail) {ans=std::max(ans,box[mxdep]+h[q[head]]);if(ans>0) return true;}
for(register int j=mxdep-1;j>=0;--j) {
++ls;++rs;
if(rs<=lstdep) {while(head<=tail&&h[q[tail]]<h[rs]) --tail;q[++tail]=rs;}
while(head<=tail&&q[head]<ls) ++head;
if(head<=tail) {ans=std::max(ans,box[j]+h[q[head]]);if(ans>0) return true;}
}
lstdep=std::max(lstdep,mxdep);
for(register int j=0;j<=mxdep;++j) h[j]=std::max(h[j],box[j]);
for(register int j=0;j<=mxdep;++j) box[j]=-0x3f3f3f3f;
}
for(register int i=0;i<=lstdep;++i) h[i]=-0x3f3f3f3f;
for(register int i=0,end=es[x].size();i<end;++i) {
edge &e=edges[es[x][i]];if(!vis[e.v]&&solve(rts[x][i])) return true;
}
return false;
}
int root;
inline bool check(double num) {
for(register int i=1;i<=idx;++i) edges[i].w-=num;
for(register int i=0;i<=n;++i) h[i]=box[i]=-0x3f3f3f3f;
ans=-0x3f3f3f3f;memset(vis,0,sizeof(vis));solve(root);
for(register int i=1;i<=idx;++i) edges[i].w+=num;
return ans>=0;
}
int main() {
scanf("%d%d%d",&n,&L,&U);
for(register int i=2;i<=n;++i) {int a,b,v;scanf("%d%d%d",&a,&b,&v);add(a,b,v);}
sum=rttot=n;getrt(1,0);build(root=rt);
double l=0,r=1e6,mid;
while(r-l>1e-4) check(mid=(l+r)/2)?l=mid:r=mid;
printf("%.3lf\n",l);
return 0;
}
|