之前学习了重链剖分，现在学习了长链剖分，遂一起写了。
重链剖分
重链剖分可以很方便地处理树上的一条链的问题。
考虑每个节点都和自己最大的儿子属于一条链，那么对于每个节点，其一直到根节点需要经过的链的数量最多只有 \(\log n\) 级别。
因为每条链链接重儿子，所以每次向上跳停下的位置，旁边一定有一个兄弟节点子树大小不小于当前子树。
然后在下一次跳跃后，这个子树也会成为当前子树的一部分。
所以子树大小增加量最小也是翻倍。
那么显然就是最多 \(\log n\) 级别了，因为卡满的条件比较苛刻，所以常数极小。
对于每个点在哪条链，直接两遍 dfs 即可。
把树转化为多条链之后，我们可以直接通过线段树等数据结构维护一些链上的修改和查询了，比较简单的方法就是先遍历重儿子，这样dfn序连续的就是一条链。
应用
洛谷 P1505 [国家集训队] 旅游
一道重链剖分的史题。
直接用树链剖分在线段树上修改和查询即可。
看看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,fa[200005],dep[200005],son[200005],siz[200005],top[200005],dfn[200005],cnt,rnk[200005],pre[200005],fr[200005];
struct P{int first,second,id;
};
vector<P> e[200005];
string s;
void dfs(int p,int f){fa[p]=f,dep[p]=dep[f]+1;son[p]=0,siz[p]=1;for(auto tmp:e[p]){int i=tmp.first,w=tmp.second,id=tmp.id;if(i==f)continue;dfs(i,p);pre[i]=w;fr[id]=i;siz[p]+=siz[i];if(siz[i]>siz[son[p]])son[p]=i;}
}
void dfs2(int p,int t){top[p]=t;dfn[p]=++cnt,rnk[cnt]=p;if(son[p])dfs2(son[p],t);for(auto tmp:e[p]){int i=tmp.first,w=tmp.second;if(i==fa[p]||i==son[p])continue;dfs2(i,i);}
}
struct ST{int c[800005],tag[800005],mx[800005],mi[800005];#define ls p<<1#define rs p<<1|1void pushup(int p){c[p]=c[ls]+c[rs];mx[p]=max(mx[ls],mx[rs]);mi[p]=min(mi[ls],mi[rs]);}void build(int p,int l,int r){tag[p]=0;if(l==r){c[p]=mx[p]=mi[p]=pre[rnk[l]];return;}int mid=l+r>>1;build(ls,l,mid),build(rs,mid+1,r);pushup(p);}void Tag(int p){c[p]=-c[p];swap(mx[p],mi[p]);mx[p]=-mx[p];mi[p]=-mi[p];tag[p]^=1;}void pushdown(int p){if(!tag[p])return;Tag(ls),Tag(rs);tag[p]=0;}void change(int p,int l,int r,int w,int v){if(l==r){c[p]=mx[p]=mi[p]=v;return;}pushdown(p);int mid=l+r>>1;if(mid>=w)change(ls,l,mid,w,v);else change(rs,mid+1,r,w,v);pushup(p);}void change2(int p,int l,int r,int L,int R){if(l>=L&&r<=R)return Tag(p);pushdown(p);int mid=l+r>>1;if(mid>=L)change2(ls,l,mid,L,R);if(mid<R)change2(rs,mid+1,r,L,R);pushup(p);}int query1(int p,int l,int r,int L,int R){if(l>=L&&r<=R)return c[p];pushdown(p);int mid=l+r>>1;if(mid>=L&&mid<R)return query1(ls,l,mid,L,R)+query1(rs,mid+1,r,L,R);if(mid>=L)return query1(ls,l,mid,L,R);return query1(rs,mid+1,r,L,R);}int query2(int p,int l,int r,int L,int R){if(l>=L&&r<=R)return mx[p];pushdown(p);int mid=l+r>>1;if(mid>=L&&mid<R)return max(query2(ls,l,mid,L,R),query2(rs,mid+1,r,L,R));if(mid>=L)return query2(ls,l,mid,L,R);return query2(rs,mid+1,r,L,R);}int query3(int p,int l,int r,int L,int R){if(l>=L&&r<=R)return mi[p];pushdown(p);int mid=l+r>>1;if(mid>=L&&mid<R)return min(query3(ls,l,mid,L,R),query3(rs,mid+1,r,L,R));if(mid>=L)return query3(ls,l,mid,L,R);return query3(rs,mid+1,r,L,R);}
}seg;
void change(int x,int y){while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])swap(x,y);seg.change2(1,1,n,dfn[top[x]],dfn[x]);x=fa[top[x]];}if(dep[y]>dep[x])swap(x,y);if(x!=y)seg.change2(1,1,n,dfn[y]+1,dfn[x]);
}
int query1(int x,int y){int ans=0;while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])swap(x,y);ans+=seg.query1(1,1,n,dfn[top[x]],dfn[x]);x=fa[top[x]];}if(dep[y]>dep[x])swap(x,y);if(x!=y)ans+=seg.query1(1,1,n,dfn[y]+1,dfn[x]);return ans;
}
int query2(int x,int y){int ans=-1e16;while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])swap(x,y);ans=max(ans,seg.query2(1,1,n,dfn[top[x]],dfn[x]));x=fa[top[x]];}if(dep[y]>dep[x])swap(x,y);if(x!=y)ans=max(ans,seg.query2(1,1,n,dfn[y]+1,dfn[x]));return ans;
}
int query3(int x,int y){int ans=1e16;while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])swap(x,y);ans=min(ans,seg.query3(1,1,n,dfn[top[x]],dfn[x]));x=fa[top[x]];}if(dep[y]>dep[x])swap(x,y);if(x!=y)ans=min(ans,seg.query3(1,1,n,dfn[y]+1,dfn[x]));return ans;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n;for(int i=1,u,v,w;i<n;i++){cin>>u>>v>>w;u++,v++;e[u].push_back({v,w,i});e[v].push_back({u,w,i});}dfs(1,0);dfs2(1,1);seg.build(1,1,n);cin>>m;for(int i=1,u,v;i<=m;i++){cin>>s>>u>>v;if(s[0]!='C')u++,v++;if(s[0]=='C')seg.change(1,1,n,dfn[fr[u]],v);else if(s[0]=='N')change(u,v);else if(s[0]=='S')cout<<query1(u,v)<<endl;else if(s[0]=='M'&&s[1]=='A')cout<<query2(u,v)<<endl;else if(s[0]=='M'&&s[1]=='I')cout<<query3(u,v)<<endl;}return 0;
}
长链剖分
长链剖分则是连接最长的儿子，其实也就是连接子树中最深的。
然后这个东西有什么用？
查询第 k 祖先
可以用长链剖分查询第 k 大的祖先，并且每次查询时间复杂度为 \(O(1)\)
我们考虑每次都先到链顶，在链顶查询。
为了保证预处理的时间复杂度和空间复杂度，我们在每个链的链顶记录这条链从上到下的点，以及反向的这个点向上的祖先。
我们如果直接找到查询点的链顶，如果深度差过大，无法查询到第 k 祖先。
因此，我们先通过倍增方法向上跳一次，此时，我们向下的距离肯定不会比到第 k 祖先小，那么可以直接就能在这个链的链顶查询了。
洛谷 P5903 【模板】树上 K 级祖先
看看代码
#include<bits/stdc++.h>
#define ui unsigned int
using namespace std;
ui s;
inline ui get(ui x) {x^=x<<13;x^=x>>17;x^=x<<5;return s=x;
}
#define int long long
int n,q,rt,dep[500005],fa[500005][20],len[500005],son[500005],top[500005],lg[500005];
vector<int> e[500005],up[500005],down[500005];
void dfs(int p,int f){fa[p][0]=f;dep[p]=dep[f]+1;for(int i=1;i<20;i++)fa[p][i]=fa[fa[p][i-1]][i-1];for(int i:e[p]){dfs(i,p);if(len[i]>len[son[p]])son[p]=i;}len[p]=len[son[p]]+1;
}
void dfs2(int p,int t){top[p]=t;if(p==t){for(int i=0,x=p;i<=len[p];i++)up[p].push_back(x),x=fa[x][0];for(int i=0,x=p;i<=len[p];i++)down[p].push_back(x),x=son[x];}if(son[p])dfs2(son[p],t);for(int i:e[p])if(i!=son[p])dfs2(i,i);
}
int query(int x,int k){if(!k)return x;int h=lg[k];x=fa[x][h];k-=(1<<h);k-=dep[x]-dep[top[x]];x=top[x];if(k>=0)return up[x][k];return down[x][-k];
}
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>q>>s;for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;for(int i=1,x;i<=n;i++){cin>>x;if(!x)rt=i;else e[x].push_back(i);}dfs(rt,0);dfs2(rt,rt);int la=0,res=0;for(int i=1;i<=q;i++){int x=(get(s)^la)%n+1;int k=(get(s)^la)%dep[x];la=query(x,k);res^=i*la;}cout<<res;return 0;
}优化dp
我们在处理一些树上 dp 时，如果遇到类似 \(f_{i,j}\) 表示第 \(i\) 个节点距离为 \(j\) 的状态时，可以考虑使用树链剖分来优化。
我们直接让每个点继承自己的长儿子的 dp 值，再和其它子树的结果进行合并，这样总状态数 \(n^2\) 就被压到了 \(n\) 级别。
那么维护也就方便了。
[WC2010] 重建计划
考虑先通过常规的套路进行二分，减去每条边的贡献，然后对于每棵树进行 dp，采用树链剖分维护，把状态压成 \(n\) 级别，用线段树维护即可。
看看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){char c=getchar();int x=0;bool f=0;while(c>'9'||c<'0'){if(c=='-')f=1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();if(f)return -x;return x;
}
int n,low,up;
vector<pair<int,int>> e[100005];
int len[100005],son[100005],st[100005],W[100005];
void dfs1(int p,int f){for(auto t:e[p]){int v=t.first,w=t.second;if(v==f)continue;dfs1(v,p);if(len[v]>len[son[p]])son[p]=v,W[p]=w;}len[p]=len[son[p]]+1;
}
struct ST{double c[400005],tag[400005];#define ls p<<1#define rs p<<1|1void pushup(int p){c[p]=max(c[ls],c[rs]);}void build(int p,int l,int r){tag[p]=0;if(l==r){c[p]=-1e18;return;}int mid=l+r>>1;build(ls,l,mid),build(rs,mid+1,r);pushup(p);}void Tag(int p,double v){c[p]+=v;tag[p]+=v;}void pushdown(int p){Tag(ls,tag[p]);Tag(rs,tag[p]);tag[p]=0;}void change(int p,int l,int r,int w,double v){if(l==r){c[p]=max(c[p],v);return;}pushdown(p);int mid=l+r>>1;if(mid>=w)change(ls,l,mid,w,v);else change(rs,mid+1,r,w,v);pushup(p);}void add(int p,int l,int r,int L,int R,double v){if(L>R)return;if(l>=L&&r<=R)return Tag(p,v);pushdown(p);int mid=l+r>>1;if(mid>=L)add(ls,l,mid,L,R,v);if(mid<R)add(rs,mid+1,r,L,R,v);pushup(p);}double query(int p,int l,int r,int L,int R){if(L>R)return -1e18;if(l>=L&&r<=R)return c[p];pushdown(p);int mid=l+r>>1;if(mid>=L&&mid<R)return max(query(ls,l,mid,L,R),query(rs,mid+1,r,L,R));if(mid>=L)return query(ls,l,mid,L,R);return query(rs,mid+1,r,L,R);}
}seg;
int now;
double res;
void dfs2(int p,int f,double vall){seg.change(1,1,n,st[p],0);if(son[p]){st[son[p]]=st[p]+1;dfs2(son[p],p,vall);seg.add(1,1,n,st[p]+1,st[p]+len[p]-1,W[p]-vall);}res=max(res,seg.query(1,1,n,st[p]+low,min(st[p]+len[p]-1,st[p]+up)));for(auto tmp:e[p]){int v=tmp.first,w=tmp.second;if(v==f||v==son[p])continue;st[v]=now;now+=len[v];dfs2(v,p,vall);for(int j=st[v],k=1;j<=st[v]+len[v]-1;j++,k++){int L=max(low-k,0ll),R=min(up-k,len[p]-1);if(L<=R)res=max(res,w-vall+seg.query(1,1,n,j,j)+seg.query(1,1,n,st[p]+L,st[p]+R));}for(int j=st[v],k=1;j<=st[v]+len[v]-1;j++,k++)seg.change(1,1,n,st[p]+k,seg.query(1,1,n,j,j)+w-vall);}
}
bool check(double x){seg.build(1,1,n);st[1]=1;now=len[1]+1;res=-1e18;dfs2(1,0,x);return res>=0;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>low>>up;for(int i=1,u,v,w;i<n;i++){cin>>u>>v>>w;e[u].push_back({v,w});e[v].push_back({u,w});}dfs1(1,0);double l=0,r=1e6;while(r-l>1e-5){double mid=(l+r)/2;if(check(mid))l=mid;else r=mid;}printf("%.3lf",l);return 0;
}