樹鏈剖分這個算法我看了好多大神們的博客，才慢慢領悟，希望我寫的過得去( ·? · )
眾所周知，維護區間信息的題目可以用線段樹高效實現。類似于區間這樣一維的結構，在樹上維護兩點間的信息【比如樹上兩點之間的最大值】也可以用線段樹嗎？ 仔細想想，好像很難實現。因為線段樹維護的是鏈狀結構，而樹是一張圖。 但我們想想，如果能把一棵樹化為一條鏈，使得要節點間編號是一段一段的【也就是有些節點間的編號是連續的，但不是所有節點間都連續】，這樣就可以通過多次調用維護區間的線段樹來實現線段樹維護樹【兩點之間有幾個連續的段就調用幾次】
這就是樹鏈剖分要做的事情：把樹分成許多條鏈，對節點重新編號，化樹為鏈，以套用其他鏈狀數據結構

怎么剖？

最好的就是剖分輕重鏈。
首先，我們先維護一些節點的信息：
siz[u] ???? 以u為根的子樹的大小 fa[u]?????? u的父親節點 dep[u]??? u的深度 son[u]??? u的重兒子 top[u]???? u所在重鏈的頂端節點 id[u]?????? 樹鏈剖分后u節點的編號
對于每一個非葉節點，它所有兒子中siz最大的那個就是它的重兒子。 對于前4項，我們可以通過一次dfs完成 看代碼： void dfs1(int u,int d,int f){int to;fa[u]=f;dep[u]=++d;siz[u]=1;for(int k=head[u];k!=-1;k=edge[k].next)if((to=edge[k].to)!=f){dfs1(to,d,u);siz[u]+=siz[to];if(!son[u]||siz[son[u]]<siz[to]) son[u]=to;}}
對于top和id,我們需要再進行一次dfs,這次dfs優先往重兒子，這樣子dfs序就是id，因為這樣你會發現： 1、對于每個重鏈，它上邊的節點編號一定是連續的 2、對于每個節點，以它為根的子樹里的所有節點一定是它接下來的那些編號【比如一個節點編號2，它為根的子樹大小6，那么接下來3、4、5、6、7一定在它的子樹里】 這兩個性質有什么用呢？ 當我們要維護兩節點間的信息時，我們只需沿著重鏈就可以套用線段樹了【因為編號是連續的】（性質1） 當我們要維護某一個子樹信息時，我們只需維護區間[id[u],id[u]+siz[u]-1]（性質2）
具體實現： void dfs2(int u,int f,int flag){id[u]=++cnt;Hash[cnt]=u;flag ? top[u]=top[f]:top[u]=u;if(son[u]) dfs2(son[u],u,1);int to;for(int k=head[u];k!=-1;k=edge[k].next){if((to=edge[k].to)!=f&&to!=son[u])dfs2(to,u,0);} }
就這樣子，我們就“剖”完了(^_^) 代碼還是很容易理解的，多打打

樹鏈剖分求LCA &樹鏈剖分+線段樹

為什么放在一起？因為這兩個玩意原理一樣。 對于節點u和v，它們在一個重鏈里，當且僅當top[u]==top[v]成立 若它們不在一個重鏈，我們不妨設top[u]的深度較大，那么我們令u=fa[top[u]]，繼續往上找。 在尋找過程中經過的路徑就是u和v之間的路徑，u最后到達的節點就是lca
這里就不在贅述了【我懶。。。】
拍上一個樹鏈剖分模板題：

洛谷P3384 【模板】樹鏈剖分

題目描述

如題，已知一棵包含N個結點的樹（連通且無環），每個節點上包含一個數值，需要支持以下操作：

操作1： 格式： 1 x y z 表示將樹從x到y結點最短路徑上所有節點的值都加上z

操作2： 格式： 2 x y 表示求樹從x到y結點最短路徑上所有節點的值之和

操作3： 格式： 3 x z 表示將以x為根節點的子樹內所有節點值都加上z

操作4： 格式： 4 x 表示求以x為根節點的子樹內所有節點值之和

輸入輸出格式

輸入格式：

?

第一行包含4個正整數N、M、R、P，分別表示樹的結點個數、操作個數、根節點序號和取模數（即所有的輸出結果均對此取模）。

接下來一行包含N個非負整數，分別依次表示各個節點上初始的數值。

接下來N-1行每行包含兩個整數x、y，表示點x和點y之間連有一條邊（保證無環且連通）

接下來M行每行包含若干個正整數，每行表示一個操作，格式如下：

操作1： 1 x y z

操作2： 2 x y

操作3： 3 x z

操作4： 4 x

?

輸出格式：

?

輸出包含若干行，分別依次表示每個操作2或操作4所得的結果（對P取模）

?

輸入輸出樣例

輸入樣例#1：
5 5 2 24 7 3 7 8 0 1 2 1 5 3 1 4 1 3 4 2 3 2 2 4 5 1 5 1 3 2 1 3 輸出樣例#1：
2 21

說明

時空限制：1s，128M

數據規模：

對于30%的數據： $N\le 10,M\le 10$

對于70%的數據： N≤103,M≤103 N \leq {10}^3, M \leq {10}^3 N≤10?3??,M≤10?3??

對于100%的數據： N≤105,M≤105 N \leq {10}^5, M \leq {10}^5 N≤10?5??,M≤10?5

?

經典的模板題，直接拍代碼，慢慢體會：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=100005,INF=200000000;inline int read(){int out=0,flag=1;char c=getchar();while(c<48||c>57) {if(c=='-') flag=-1;c=getchar();}while(c>=48&&c<=57) {out=out*10+c-48;c=getchar();}return out*flag; }int N,M,rt,P; int A[maxn];int head[maxn],nedge=0; struct EDGE{int to,next; }edge[2*maxn];inline void build(int a,int b){edge[nedge]=(EDGE){b,head[a]};head[a]=nedge++;edge[nedge]=(EDGE){a,head[b]};head[b]=nedge++; }int siz[maxn],fa[maxn],son[maxn],dep[maxn],top[maxn],id[maxn],Hash[maxn],cnt=0;void dfs1(int u,int d,int f){int to;fa[u]=f;dep[u]=++d;siz[u]=1;for(int k=head[u];k!=-1;k=edge[k].next)if((to=edge[k].to)!=f){dfs1(to,d,u);siz[u]+=siz[to];if(!son[u]||siz[son[u]]<siz[to]) son[u]=to;}}void dfs2(int u,int f,int flag){id[u]=++cnt;Hash[cnt]=u;flag ? top[u]=top[f]:top[u]=u;if(son[u]) dfs2(son[u],u,1);int to;for(int k=head[u];k!=-1;k=edge[k].next){if((to=edge[k].to)!=f&&to!=son[u])dfs2(to,u,0);} }int L,R,sum[4*maxn],lazy[4*maxn];void build(int u,int l,int r){if(l==r) sum[u]=A[Hash[l]];else{int mid=(l+r)>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);sum[u]=(sum[u<<1]+sum[u<<1|1])%P;} }void pd(int u,int l,int r){int mid=(l+r)>>1;sum[u<<1]=(sum[u<<1]+lazy[u]*(mid-l+1)%P)%P;sum[u<<1|1]=(sum[u<<1|1]+lazy[u]*(r-mid)%P)%P;lazy[u<<1]=(lazy[u<<1]+lazy[u])%P;lazy[u<<1|1]=(lazy[u<<1|1]+lazy[u])%P;lazy[u]=0; }void add(int u,int l,int r,int v){if(l>=L&&r<=R) {sum[u]=(sum[u]+(r-l+1)*v%P)%P;lazy[u]=(lazy[u]+v)%P;}else{if(lazy[u]) pd(u,l,r);int mid=(l+r)>>1;if(mid>=L) add(u<<1,l,mid,v);if(mid<R) add(u<<1|1,mid+1,r,v);sum[u]=(sum[u<<1]+sum[u<<1|1])%P;} }int Query(int u,int l,int r){if(l>=L&&r<=R) return sum[u];else{if(lazy[u]) pd(u,l,r);int mid=(l+r)>>1;if(mid>=R) return Query(u<<1,l,mid);else if(mid<L) return Query(u<<1|1,mid+1,r);else return (Query(u<<1,l,mid)+Query(u<<1|1,mid+1,r))%P;} }void solve1(int u,int v,int x){while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]]) swap(u,v);L=id[top[u]];R=id[u];add(1,1,N,x);u=fa[top[u]];}if(id[u]>id[v]) swap(u,v);L=id[u];R=id[v];add(1,1,N,x); }void solve2(int u,int v){int ans=0;while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]]) swap(u,v);L=id[top[u]];R=id[u];ans=(ans+Query(1,1,N))%P;u=fa[top[u]];}if(id[u]>id[v]) swap(u,v);L=id[u];R=id[v];ans=(ans+Query(1,1,N))%P;printf("%d\n",ans); }void solve3(int u,int v){L=id[u];R=id[u]+siz[u]-1;add(1,1,N,v); }void solve4(int u){L=id[u];R=id[u]+siz[u]-1;printf("%d\n",Query(1,1,N)); }int main() {fill(head,head+maxn,-1);N=read();M=read();rt=read();P=read();int a,b,cmd;for(int i=1;i<=N;i++) A[i]=read();for(int i=1;i<N;i++){a=read();b=read();build(a,b);}dfs1(rt,0,0);dfs2(rt,0,0);//for(int i=1;i<=N;i++) printf("%d ",Hash[i]);cout<<endl;build(1,1,N);while(M--){cmd=read();a=read();switch(cmd){case 1:b=read();solve1(a,b,read());break;case 2:b=read();solve2(a,b);break;case 3:b=read();solve3(a,b);break;case 4:solve4(a);break;default:break;}}return 0; }

?

?

??

?

轉載于:https://www.cnblogs.com/Mychael/p/8282897.html

總結

以上是生活随笔為你收集整理的树链剖分原理与应用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。