南京学网站建设/班级优化大师怎么用

关于长链剖分
两个应用

• $O(n)$ 统计每个点子树中可合并的以深度为下标的信息
• 经过一些预处理，单次$O(1)$在线查询一个点的$k$级祖先

这题二分答案后就是求长度在区间内的最长链 然后就记录下某个深度的最大dis 长链剖分加线段树 维护 $O(n\log ^2n)$
从轻儿子合并来的时候顺便更新答案

竟然比点分慢

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef double ld;inline char nc(){static char buf[100000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x){char c=nc(),b=1;for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}const int N=100005;int n;
ld T[N<<2]; int back[N];
inline void Build(int x,int l,int r){T[x]=-1e20;if (l==r) return void(back[l]=x);int mid=(l+r)>>1;Build(x<<1,l,mid); Build(x<<1|1,mid+1,r);
}
inline void modify(int x,int l,int r,int t,ld a){/*T[x]=max(T[x],a);if (l==r) return;int mid=(l+r)>>1;if (t<=mid) modify(x<<1,l,mid,t,a);else modify(x<<1|1,mid+1,r,t,a);*/x=back[t];while (x) T[x]=max(T[x],a),x>>=1;
}
inline ld query(int x,int l,int r,int ql,int qr){if (ql<=l && r<=qr) return T[x];int mid=(l+r)>>1; ld ret=-1e20;if (ql<=mid) ret=max(ret,query(x<<1,l,mid,ql,qr));if (qr>mid) ret=max(ret,query(x<<1|1,mid+1,r,ql,qr));return ret;
}struct edge{int u,v,next; ld w;
}G[N<<1];
int head[N],inum;
inline void add(int u,int v,ld w,int p){G[p].u=u; G[p].v=v; G[p].w=w; G[p].next=head[u]; head[u]=p;
}
#define V G[p].vint fat[N],depth[N],Dep[N];inline void dfs(int u,int fa){Dep[u]=depth[u]=depth[fa]+1; fat[u]=fa;for (int p=head[u];p;p=G[p].next)if (V!=fa)dfs(V,u),Dep[u]=max(Dep[u],Dep[V]);
}
int top[N],son[N];
int tid[N],clk;
inline void find(int u,int fa,int z){tid[u]=++clk; top[u]=z;son[u]=0; int maxv=0;for (int p=head[u];p;p=G[p].next)if (V!=fa && Dep[V]>maxv)maxv=Dep[son[u]=V];if (son[u]) find(son[u],u,z);for (int p=head[u];p;p=G[p].next)if (V!=fa && V!=son[u])find(V,u,V);
}int L,R;ld dis[N];
ld ret;ld tmp[N];inline ld QQ(int u,int L,int R){if (R<0) return -1e20;L=max(L,0);if (depth[u]+L<=Dep[u])return query(1,1,n,tid[u]+L,tid[u]+min(R,Dep[u]-depth[u]));return -1e20;
}inline void dp(int u,int fa){modify(1,1,n,tid[u],dis[u]);for (int p=head[u];p;p=G[p].next)if (V==son[u]){dis[V]=dis[u]+G[p].w,dp(V,u);}for (int p=head[u];p;p=G[p].next)if (V!=fa && V!=son[u]){dis[V]=dis[u]+G[p].w,dp(V,u);for (int j=1;j<=Dep[V]-depth[V]+1;j++){tmp[j]=T[back[tid[V]+j-1]];ret=max(ret,tmp[j]+QQ(u,L-j,R-j)-2*dis[u]);}for (int j=1;j<=Dep[V]-depth[V]+1;j++)modify(1,1,n,tid[u]+j,tmp[j]);}ret=max(ret,QQ(u,L,R)-dis[u]);
}inline bool check(ld mid){for (int i=1;i<=inum;i++) G[i].w-=mid;ret=-1e20;Build(1,1,n);dis[1]=0; dp(1,0);for (int i=1;i<=inum;i++) G[i].w+=mid;return ret>=-1e-5;
}int main(){int x,y,w;freopen("t.in","r",stdin);freopen("t.out","w",stdout);read(n); read(L); read(R);for (int i=1;i<n;i++)read(x),read(y),read(w),add(x,y,w,++inum),add(y,x,w,++inum);dfs(1,0); find(1,0,1);ld L=0,R=1e10,MID;while (R-L>1e-5)if (check(MID=(L+R)/2))L=MID;elseR=MID;printf("%.3lf\n",(L+R)/2);return 0;
}