include<bits/stdc++.h>

using namespace std;

define int long long

namespace yspm{
inline int read()
{
int res=0,f=1; char k;
while(!isdigit(k=getchar())) if(k‘-‘) f=-1;
while(isdigit(k)) res=res10+k-‘0‘,k=getchar();
return resf;
}
const int N=2e5+10;
const double eps=1e-4;
int siz,minn,sz[N],rt,n,l,r,f[N],dep[N],q[N],q1[N],beg,fin;
struct node{
int to,nxt;
double dis;
}e[N<<1];
int head[N],cnt; double dis[N],maxx[N];
bool vis[N];
inline void add(int u,int v,double w)
{
e[++cnt].to=v; e[cnt].dis=w; e[cnt].nxt=head[u];
return head[u]=cnt,void();
}//原树相关
inline void getrt(int x,int fa)
{
sz[x]=1; int tmp=0;
for(int i=head[x];i;i=e[i].nxt)
{
int t=e[i].to;
if(vis[t]||tfa) continue;
getrt(t,x); sz[x]+=sz[t]; tmp=max(tmp,sz[t]);
} tmp=max(tmp,siz-sz[x]);
if(tmp<minn) rt=x,minn=tmp;
return ;
}
int fa[N];
inline bool check(int id,double x)
{
int md=0;
for(int rec=head[id];rec;rec=e[rec].nxt)
{
int t=e[rec].to; if(vis[t]) continue;
//bfs搞子树信息
beg=0; fin=1; q[0]=t; fa[t]=id; dis[t]=e[rec].dis-x; dep[t]=1;
while(beg!=fin)
{
int fr=q[beg]; ++beg;
for(int i=head[fr];i;i=e[i].nxt)
{
int tt=e[i].to; if(vis[tt]||tt==fa[fr]) continue; fa[tt]=fr;
dis[tt]=e[i].dis+dis[fr]-x; dep[tt]=dep[fr]+1; q[fin]=tt; fin++;
}
}
//这里的q和fin和beg都是在bfs子树的时候的
int st=1,ed=0,now=md;//now是原来深度的最大值
for(int i=0;i<fin;++i)
{
int x=q[i];
while(now>=0&&dep[x]+now>=l)
{
while(st<=ed&&maxx[now]>maxx[q1[ed]]) --ed;
q1[++ed]=now; now--;//更新相关深度的信息
}
while(st<=ed&&dep[x]+q1[st]>r) ++st;
if(st<=ed&&dis[x]+maxx[q1[st]]>=0) return 1;
}//q1这里是单调递减的维护深度的序列，维护的是原来子树的信息，里面存的是深度值
for(int i=md+1;i<=dep[q[fin-1]];++i) maxx[i]=-1e18-10;
for(int i=0;i<fin;++i)
{
int x=q[i];
maxx[dep[x]]=max(maxx[dep[x]],dis[x]);
}
//更新对应深度的最大值
md=max(md,dep[q[fin-1]]);
} return 0;
}
double ed,ans,st;
inline void calc(int x)
{
double L=ans,R=ed;
while(R-L>eps)
{
double mid=(L+R)/2;
if(check(x,mid)) L=mid; else R=mid;
} ans=L;
return ;
}
inline void dfs(int x)
{
vis[x]=1; calc(x);
for(int i=head[x];i;i=e[i].nxt)
{
int t=e[i].to; if(vis[t]) continue;
siz=sz[t]; minn=1e18+10; getrt(t,0);
if(sz[t]>l) dfs(rt);
} return ;
}
signed main()
{
n=read(); l=read(); r=read();
for(int i=1,u,v;i<n;++i)
{
double w;
u=read(),v=read(),scanf("%lf",&w);
add(u,v,w),add(v,u,w),ed=max(ed,w); st=min(st,w);
} ans=st; minn=1e18+10; siz=n; getrt(1,0); dfs(rt);
printf("%.3lf\n",ans);
return 0;
}
}
signed main(){return yspm::main();}

Luogu4292 WC2010重建计划

原文：https://www.cnblogs.com/yspm/p/13386401.html