zhang • 3个月前
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; } vectors[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\n",abs(ans));
}
int main() {
freopen("pp.in","r",stdin);
freopen("pp.out","w",stdout);
work();
return 0;
}
评论: