分数规划和长链剖分大体思路大佬们已经讲得很清楚了 奈何我太蒟了被有个问题卡了我很久 就是怎么分配每个子树对应的线段树的空间
当我们正在处理 x 点时 先递归处理完它的重儿子也就是 y 然后直接让 x 继承 y 的数据 若 y 对应的数组长这样子 我们发现在 y 这棵树中 x 为距离 1 的点就是 y 距离 0 的点 x 为距离 2 的点就是 y 距离 1 的点… 所以这个显然就是 我们先遍历重儿子所形成的 dfs 序 其中每一条长链都对应的一段区间
所以这道题就是对 dfs 序建一颗线段树 x子树中 距离为n的点的最大权值 对应的是线段树中第 dfn[x]+n 个元素
我也搞不懂为什么我在这种显zhi然zhang的地方卡这么久 最外层的二分一个log 线段树一个log O ( n l o g 2 n ) O(nlog^2n) O(nlog2n) 最后代码
#include <bits/stdc++.h> #define N 100100 #define M 200100 #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r #define mid ((l+r)>>1) using namespace std; typedef long long ll; const double inf=-5e11*1.0; int n,minn,maxx; int f[N],nxt[M],data[M],num; int dfn[N],mdep[N],dep[N],son[N],fa[N],len[N],root,ti; double rr,mm,lst[N],far[M],dis[N]; int posi[N]; bool ans; struct _tr{ double t[N<<3]; inline void push_up(int rt){ t[rt]=max(t[rt<<1],t[rt<<1|1]); } inline void updata(int pos,double c,int rt=1,int l=1,int r=n){ if(l==r){ t[rt]=max(c,t[rt]); return; } if(pos<=mid){ updata(pos,c,lson); } else{ updata(pos,c,rson); } push_up(rt); } inline double query(int L,int R,int rt=1,int l=1,int r=n){ if(L<=l&&r<=R)return t[rt]; double res=inf; if(L<=mid)res=max(res,query(L,R,lson)); if(R>mid)res=max(res,query(L,R,rson)); return res; } inline void build(int rt=1,int l=1,int r=n){ t[rt]=inf; if(l==r){ posi[l]=rt; return; } build(lson); build(rson); } }q; void inline add(int x,int y,int z){ nxt[++num]=f[x]; f[x]=num; data[num]=y; far[num]=z; } inline void dfs(int x){ int y; for(int i=f[x];i;i=nxt[i]){ y=data[i]; if(y==fa[x])continue; lst[y]=far[i]; fa[y]=x; dep[y]=mdep[y]=dep[x]+1; dfs(y); if(mdep[x]<mdep[y]){ son[x]=y; mdep[x]=mdep[y]; } } len[x]=mdep[x]-dep[x]; } inline void dfs2(int x){ dfn[x]=++ti; if(son[x]){ dfs2(son[x]); } int y; for(int i=f[x];i;i=nxt[i]){ y=data[i]; if(y==fa[x]||y==son[x])continue; dfs2(y); } } inline void solve(int x){ int y=son[x],o=dfn[x],ql,qr,oo; double z; q.updata(o,dis[x]); if(y){ dis[y]=dis[x]+lst[y]-mm; solve(y); if(ans==1)return; } for(int i=f[x];i;i=nxt[i]){ y=data[i]; if(y==fa[x]||y==son[x])continue; dis[y]=dis[x]+lst[y]-mm; solve(y); if(ans==1)return; oo=dfn[y]; for(int j=0;j<=min(maxx,len[y]);j++){ ql=max(minn-1-j,0),qr=min(maxx-1-j,len[x]); if(ql>qr)continue; z=q.t[posi[oo+j]]-dis[x]; if(q.query(o+ql,o+qr)-dis[x]+z>=0){ ans=1; return; } } for(int j=0;j<=min(len[y],maxx);j++){ ql=1+j; if(q.t[posi[oo+j]]>q.t[posi[o+ql]]){ q.updata(o+ql,q.t[posi[oo+j]]); } } } if(len[x]>=minn){ if(q.query(o+minn,o+min(len[x],maxx))>=dis[x]){ ans=1; return; } } } void get_ans(){ double l=0,r=rr; while(r-l>0.0002){ mm=(l+r)/2.0000; ans=0; dis[root]=0; q.build(); solve(root); if(ans){ l=mm; } else{ r=mm; } } printf("%.3lf",l); } int main(){ // freopen("test.in","r",stdin); scanf("%d %d %d",&n,&minn,&maxx); int u,v,z; for(int i=1;i<n;i++){ scanf("%d %d %d",&u,&v,&z); add(u,v,z); add(v,u,z); rr=max((double)z,rr); } root=rand()%n+1; dfs(root); dfs2(root); get_ans(); return 0; }