题目传送门
分析看到比值的形式就想到 \(01分数规划\)，二分答案
设当前的值为 \(mids\)
如果存在\(\frac{\sum _{e \in S} v(e)}{|S|} \geq mids\)
那么 \(\sum _{e \in S} v(e)-|S| \times mids \geq 0\)
我们把每一条边的权值减去 \(mids\)
问题就变成了找出一条长度在 \([l,r]\) 之间的简单路径
是的路径的长度大于等于 \(0\)
我们可以开一个权值线段树去维护，但这样复杂度就变成了 \(nlog^3n\)
实际上，我们可以把寻找路径时的 \(dfs\) 换成 \(bfs\)
这样就相当于自动给路径的长度排好了序，可以直接用单调队列维护
因为每一次单调队列都要从 \(0\) 枚举到 \(min(r,maxdep)\)
因为你记录最大值的数组最多只会更新到 \(maxdep\)，所以枚举多了没用
为了保证复杂度，我们要提前把子树按照子树内最大深度从小到大排序，使得 \(maxdep\) 尽可能小
还可以提前建出点分树，避免每一次 \(dfs\) 重新找重心浪费时间
时间复杂度 \(nlog^2n\)
代码 #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> #include<vector> #define rg register inline int read(){ rg int x=0,fh=1; rg char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') fh=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*fh; } const int maxn=4e5+5; int h[maxn],tot=1,n,m,lef,rig; struct asd{ int to,nxt,preval; double val; }b[maxn]; void ad(rg int aa,rg int bb,rg int cc){ b[tot].to=bb; b[tot].nxt=h[aa]; b[tot].preval=cc; h[aa]=tot++; } struct Node{ int num,dep,id; Node(){} Node(rg int aa,rg int bb,rg int cc){ num=aa,dep=bb,id=cc; } }; std::vector<Node> pre[maxn]; bool cmp(rg Node aa,rg Node bb){ return aa.dep<bb.dep; } int dep[maxn]; void dfs(rg int now,rg int lat,rg int nowdep){ dep[now]=nowdep; for(rg int i=h[now];i!=-1;i=b[i].nxt){ rg int u=b[i].to; if(u==lat) continue; dfs(u,now,nowdep+1); dep[now]=std::max(dep[now],dep[u]); } }//预处理子树最大深度 int siz[maxn],maxsiz[maxn],rt,totsiz,jud[maxn],tim,tp; bool vis[maxn]; std::vector<int> g[maxn]; void getroot(rg int now,rg int lat){ siz[now]=1,maxsiz[now]=0; for(rg int i=h[now];i!=-1;i=b[i].nxt){ rg int u=b[i].to; if(u==lat || vis[u]) continue; getroot(u,now); siz[now]+=siz[u]; maxsiz[now]=std::max(maxsiz[now],siz[u]); } maxsiz[now]=std::max(maxsiz[now],totsiz-siz[now]); if(maxsiz[now]<maxsiz[rt]) rt=now; }//找重心 void predfs(rg int now){ vis[now]=1; for(rg int i=h[now];i!=-1;i=b[i].nxt){ rg int u=b[i].to; if(!vis[u]){ pre[now].push_back(Node(u,dep[u],i)); } } std::sort(pre[now].begin(),pre[now].end(),cmp); for(rg int i=0;i<pre[now].size();i++){ rg int u=pre[now][i].num; totsiz=siz[u],rt=0; getroot(u,now); g[now].push_back(rt); predfs(rt); } }//建好点分树，并按照最大深度从小到大排序 double ans=-1e7,mmax[maxn]; struct jie{ double val; int dep; jie(){} jie(rg double aa,rg int bb){ val=aa,dep=bb; } }sta[maxn]; int q1[maxn],q2[maxn],nhead,ntail; double q3[maxn]; void bfs(rg int now,rg double nval,rg int ndep){ tim++; jud[now]=tim,nhead=ntail=1; q1[1]=now,q2[1]=ndep,q3[1]=nval; rg int now1,now2; rg double now3; while(nhead<=ntail){ now1=q1[nhead],now2=q2[nhead],now3=q3[nhead]; sta[++tp]=jie(now3,now2); nhead++; for(rg int i=h[now1];i!=-1;i=b[i].nxt){ rg int u=b[i].to; if(jud[u]==tim || vis[u]) continue; jud[u]=tim; ntail++; q1[ntail]=u,q2[ntail]=now2+1,q3[ntail]=now3+b[i].val; } } }//bfs寻找路径 int q[maxn],head,tail; void solve(rg int now){ vis[now]=1,tp=1; rg int beg=0,cs=0,tl=0,tr=0,maxdep=0; mmax[0]=0; for(rg int i=0;i<pre[now].size();i++){ rg int u=pre[now][i].num; beg=tp+1; bfs(u,b[pre[now][i].id].val,1); head=1,tail=0,cs=beg; for(rg int j=std::min(rig,maxdep);j>=0;j--){ tl=j>=lef?0:lef-j,tr=rig-j; while(head<=tail && sta[q[head]].dep<tl) head++; while(cs<=tp && sta[cs].dep<tl) cs++; while(cs<=tp && sta[cs].dep<=tr){ while(head<=tail && sta[cs].val>=sta[q[tail]].val) tail--; q[++tail]=cs++; } if(head<=tail) ans=std::max(ans,sta[q[head]].val+mmax[j]); } for(rg int j=beg;j<=tp;j++) mmax[sta[j].dep]=std::max(mmax[sta[j].dep],sta[j].val); maxdep=std::max(maxdep,sta[tp].dep); } if(ans>=0) return; for(rg int i=1;i<=tp;i++) mmax[sta[i].dep]=-1e9; for(rg int i=0;i<g[now].size();i++) solve(g[now][i]); }//点分治核心+单调队列 bool pd(rg double mids){ memset(vis,0,sizeof(vis)); memset(jud,0,sizeof(jud)); for(rg int i=0;i<maxn;i++) mmax[i]=-1e7; ans=-1e7,tim=0; for(rg int i=1;i<tot;i++) b[i].val=(double)b[i].preval-mids; solve(rt); return ans>=0; }//判断答案是否合法 int main(){ memset(h,-1,sizeof(h)); n=read(),lef=read(),rig=read(); rg int aa,bb,cc; for(rg int i=1;i<n;i++){ aa=read(),bb=read(),cc=read(); ad(aa,bb,cc); ad(bb,aa,cc); } dfs(1,0,0); maxsiz[0]=0x3f3f3f3f,rt=0,totsiz=n; getroot(1,0); predfs(rt); totsiz=n,rt=0; memset(vis,0,sizeof(vis)); getroot(1,0); double l=0,r=1e6,mids; for(rg int i=1;i<=33;i++){ mids=(l+r)/2.0; if(pd(mids)) l=mids; else r=mids; } printf("%.3f\n",mids); return 0; }