---

在学树链剖分之前，我们先得理解什么是树链剖分，以及它的应用

那么，什么是树链剖分呢(～￣▽￣)～

树链剖分就是将树分割成多条链，然后利用数据结构（线段树、树状数组等）来维护这些链。

看上去好像很好理解的样子！（实际上也的确是这样……），咳咳，那它到底有什么应用，先看一道水题：

---

e.g

给你一颗有根树，对区间进行两种操作：1.路径值修改（树上差分？）；2.查询路径和（LCA？）；

确实水到不行= =

我们想要在低时间复杂度的情况下完成这两个操作，用求LCA的方法显然是不现实的，每次修改后都会花费\(O（n）\)的时间复杂度\(dfs\)更新\(dis\)值（老东西，你的LCA最没用了）

（求路径和原理：\(Ans=dis[x]+dis[y]-2*lca(x,y)\)），当然，树链剖分可以解决的问题当然不是这种水题，这道题只是为了引路（老东西，你的水题最没用了）。

---

在正式开始学习树链剖分之前，我们先来看一些概念：

一些概念：

重儿子（吃的好的儿子）：儿子中子树中节点个数最大的儿子

轻儿子（吃的不好的儿子）：非重儿子的儿子

重边：连接父亲与重儿子的边

轻边：连接父亲与轻儿子的边

重链：重边构成的一条链

轻链：轻边构成的一条链

如图：

图中红色的边就是重边，而重边所连接的点就是重节点，而标上红色五角星的点就是后文的\(top\)节点，从图中我们也可以显然的发现，轻边上的叶子节点必然是\(top\)节点，我们之后也会用到

变量声明：

\(dfn\)：记录遍历后的\(dfs\)序

\(pos\)：记录\(dfs\)之后各节点在\(dfn\)中的编号（树上问题区间问题的思想）

\(top\)：重链的起点

\(dep\)：深度

\(sz\)：子节点个数

\(son\)：重儿子编号

---

那么，我们就要开始具体实现树链剖分啦！

首先，我们需要进行两次\(dfs\)：

1.记录深度维护重儿子父节点

2.连接重链，维护\(top\)节点，dfs序

为什么我们不在第一次ds中就维护所有的信息呢？因为：我们希望优先将重链连接起来，使其在\(dfn\)中成为连续的一个区间；当我们在选择重儿子时如果有多个儿子子节点个数相同，我们只需要随便选择一个就好。（此乃自然之理）

dfs1 code

void dfs1(ll x,ll pre){    ll siz=G[x].size();    sz[x]++;    dep[x]=dep[pre]+1;    fa[x]=pre;    for(ll i=0,p=G[x][i]; i
    
     sz[son[x]]) son[x]=p;//更新重儿子    }}
    

dfs2 code

void dfs2(ll x,ll t,ll pre){    top[x]=t;//继承父亲的top    dfn[++tot]=x;    pos[x]=tot;    if(!son[x]) return;    dfs2(son[x],t,x);//优先更新重儿子    ll siz=G[x].size();    for(int i=0,p=G[x][i]; i

那么我们如何解决查询操作呢：

ll solve(ll x,ll y){    ll ans=0,fx=top[x],fy=top[y];    for(; fx!=fy;x=fa[x],fx=top[x]) {        if(dep[fx]
    
     pos[y]) swap(x,y);    ans+=query(root,1,maxn,pos[x],pos[y],0);    return ans;}
    

从代码中我们也可以看出，这跟倍增的思想非常相似,只不过这里是使用top进行加速罢了

---

树链剖分的性质：

1.对于任意轻边\((u,v)\)，\(size(u)/2>size(v)\)

2.从根节点到任意节点经过的轻重链个数不会超过\(log_2 N\)

(板题)

\(code:\)

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;char buf[1<<20],*p1,*p2;inline char gc(){//  return getchar();    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==p1?0:*p1++;}template
        
         inline void read(T &x){    char tt;    bool flag=0;    while(!isdigit(tt=gc())&&tt!='-');    tt=='-'?(flag=1,x=0):(x=tt-'0');    while(isdigit(tt=gc())) x=x*10+tt-'0';    if(flag) x=-x;}const int maxn=30002;int n,q,tot,M=1;int son[maxn],sz[maxn],top[maxn],fa[maxn],dep[maxn],pos[maxn];int sum[maxn<<2],mx[maxn<<2];vector
         
          G[maxn];void dfs(int x,int pre){ dep[x]=dep[pre]+1; fa[x]=pre;sz[x]++; for(int i=G[x].size()-1;i>=0;i--) { int p=G[x][i]; if(p==pre) continue; dfs(p,x);sz[x]+=sz[p]; if(sz[p]>sz[son[x]]) son[x]=p; }} void dfs(int x,int pre,int t){ top[x]=t;pos[x]=++tot; if(!son[x]) return; dfs(son[x],x,t); for(int i=G[x].size()-1;i>=0;i--) { int p=G[x][i]; if(p==pre || p==son[x]) continue; dfs(p,x,p); }}#define ls p<<1#define rs p<<1|1void update(int p){ mx[p]=max(mx[ls],mx[rs]); sum[p]=sum[ls]+sum[rs]; }void merge(int &x,int y){x=max(x,y);}void add(int &x,int y){x+=y;}void modify(int x,int d){ x+=M;mx[x]=d,sum[x]=d; while(x>>=1) update(x);}int getsum(int x,int y){ int ans=0; for(x+=M-1,y+=M+1;x^y^1;x>>=1,y>>=1) { if(~x&1) add(ans,sum[x^1]); if( y&1) add(ans,sum[y^1]); } return ans;}int getmx(int x,int y){ int ans=-1e9; for(x+=M-1,y+=M+1;x^y^1;x>>=1,y>>=1) { if(~x&1) merge(ans,mx[x^1]); if( y&1) merge(ans,mx[y^1]); } return ans;}void solve1(int x,int y){ if(x==y){printf("%d\n",mx[pos[x]+M]);return;} int ans=-1e9; while(top[x]^top[y]) { if(dep[top[x]]>=dep[top[y]]) { merge(ans,getmx(pos[top[x]],pos[x])); x=fa[top[x]]; } else { merge(ans,getmx(pos[top[y]],pos[y])); y=fa[top[y]]; } } if(dep[x]>dep[y]) swap(x,y); merge(ans,getmx(pos[x],pos[y])); printf("%d\n",ans);}void solve2(int x,int y){ if(x==y){printf("%d\n",sum[pos[x]+M]);return;} int ans=0; while(top[x]^top[y]) { if(dep[top[x]]>=dep[top[y]]) { add(ans,getsum(pos[top[x]],pos[x])); x=fa[top[x]]; } else { add(ans,getsum(pos[top[y]],pos[y])); y=fa[top[y]]; } } if(dep[x]>dep[y]) swap(x,y); add(ans,getsum(pos[x],pos[y])); printf("%d\n",ans);}int main(){// freopen("count1.in","r",stdin);// freopen("count1.out","w",stdout); read(n);while(M<=n)M<<=1; for(int i=1;i
          
           =1;i--) update(i); read(q); while(q--) { char tt; int x,y; while((tt=gc())!='H'&&tt!='M'&&tt!='S'); read(x),read(y); if(tt=='H') modify(pos[x],y); if(tt=='M') solve1(x,y); if(tt=='S') solve2(x,y); }}
          
         
        
       
      
     
    

---

习题