文章目錄

• 概念
• 模板
• 例題1：軟件包管理器
• • 題目
  • 題解
  • 代碼實現
• 例題2：POJ3237 tree
• • 題目
  • 題解
  • 代碼實現

概念

樹鏈剖分主要是用于解決以下這兩個問題。

1、更改樹上點x到點y的最短路徑上的所有結點的值
2、查詢樹上點x到點y的最短路徑上的所有結點的和。

---

在講樹鏈剖分之前，我們先來看一下這樣幾個概念：

重兒子：父親結點的所有兒子結點中，子樹擁有結點數最多的結點。
輕兒子：父親結點除了重兒子以外的所有兒子。
重邊：父親結點與重兒子的連邊。
輕邊：父親結點與輕兒子的連邊。
重鏈：所有重邊所組成的一條鏈。

在這幅圖中，圈內的數字為每個點的權值，粗邊為重邊，組成的鏈稱為重鏈

---

任意一個點到根結點的路徑，不會有超過logn條輕邊；重鏈的個數不超過logn；
每個點一定都會只屬于一個重鏈
接下來進入證明$logn$條輕邊環節（其余的相信大家都能自己$finishit$）
法一：（表達頗為復雜，可移至法二）

我們假設$x??fa$是輕邊，$x^{\prime }??fa$是重邊，那么就有$size[x]\le size[x^{\prime }],size[x]<size[fa]$
為什么沒有取等，因為$fa$自己也算一個$size$
所以最極限的情況就是$size[fa]=size[x]+size[x^{\prime }]+1,size[x]=size[x^{\prime }]$，也是嚴格大于

那么如果$x??fa$是輕邊，那么$size[fa]$至少是$size[x]$兩倍（粗略來看），如果$fa$也是輕邊往上又$\times 2$以此類推
那么就是$2^i$（i只是我用來表示形式搞的），而點總共只有$n$，故$i\le logn$，所以上線就是$logn$

法二：（本質與法一一樣，但是表述要好懂一點吧。。。
根據輕兒子重兒子的定義，我們不難得到$siz[輕兒子]<=\frac{siz[父親]}{2}$，這么滾雪球般的$/2$，就是$log$的級別

然后，知道重鏈和重鏈之間至少隔了一條輕邊（否則兩條重鏈應該合并成一條）
極限情況就是，每兩條輕邊之間就插一條重鏈，輕邊的級別都被限制在了$log$
所以重鏈的級別也不會超過$log$

---

模板

接下來我們講講實現：
在進行樹鏈剖分時，我們將進行這些變量聲明：
f[u]:保存點u的父親結點
d[u]:保存點u的深度
size[u]:保存以u為根節點的子樹的結點個數
son[u]:保存點u的重兒子
top[u]:保存點u所在重鏈的頂端結點
id[u]:保存點u在線段樹上對應的編號
rk[u]：表示線段樹上點u在原樹上對應的編號（與id進行映射）

---

接下來，就是要求出所有結點它的子樹的大小,并找出重兒子（即處理出size[u]和son[u]）。我們在這里可以直接通過DFS，對樹進行深度搜索，得到我們想要的兩個答案。

void dfs1 ( int u, int fa, int depth ) { //當前節點，父節點，層次深度 f[u] = fa;d[u] = depth;size[u] = 1;//這個點本身size=1 for ( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i];if ( v == fa ) continue;dfs1 ( v, u, depth + 1 );//層次深度+1 size[u] += size[v];//回溯的子節點size已被處理，用它來更新父節點size if ( size[v] > size[son[u]] || ! son[u] )son[u] = v;//選取size最大的作為重兒子 } }

接下來，我們再進行一遍DFS，找到所有結點重鏈的頂端，并對結點進行重新排序。

void dfs2 ( int u, int t ) { //當前節點，重鏈頂端 top[u] = t;id[u] = ++ cnt; //標記dfs序 rk[cnt] = u;//序號cnt對應節點u 一般來說是沒有用的。。 if ( ! son[u] ) return;dfs2 ( son[u], t );/*我們選擇優先進入重兒子來保證一條重鏈上各個節點dfs序號連續一個點和它的重兒子處于同一條重鏈所以重兒子所在重鏈的頂端還是t */for ( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i];if ( v != son[u] && v != f[u] )dfs2 ( v, v );//一個點位于輕鏈頂端，那么他的top必定是它本身 } }

兩遍DFS之后，我們就可以知道我們前面列出的所有變量的值
且對于每一條重鏈，他們當中的點都是連續的區間

對于點$u$而言，$u$的子樹的$dfs$序都是連續的一段區間

那么，對于每一條重鏈，我們可以通過線段樹去維護這一條鏈內的所有信息
對于兩個點不在一條鏈上的，我們可以通過對深度較深的那個點進行操作
將這個點跳轉到他的top位置的父親結點上，直到兩個點在一條重鏈上為止

寫法很多，分享其一

int sum ( int x, int y ) {int ans = 0, fx = top[x], fy = top[y];while ( fx != fy ) {if ( d[fx] >= d[fy] ) {ans += query ( 1, cnt, id[fx], id[x], 1 );//線段樹的區間從0或者1開始由題決定//線段樹l,r,我們要查找的區間L,R,線段樹編號numx = f[fx];fx = top[x]; }else {ans += query ( 1, cnt, id[fy], id[y], 1 );y = f[fy];fy = top[y];}}//循環結束，兩點已經位于同一條重鏈上，但兩點不一定為同一個點//所以我們還要統計這兩點間的貢獻 if ( id[x] <= id[y] )ans += query ( 1, cnt, id[x], id[y], 1 );else ans += query ( 1, cnt, id[y], id[x], 1 );return ans; }

線段樹的模板我就不給了，注意要打lazy標記哦！！！
接下來就去戰場上試試手吧。。

例題1：軟件包管理器

題目

題目描述
Linux用戶和OSX用戶一定對軟件包管理器不會陌生。通過軟件包管理器，你可以通過一行命令安裝某一個軟件包，然后軟件包管理器會幫助你從軟件源下載軟件包，同時自動解決所有的依賴（即下載安裝這個軟件包的安裝所依賴的其它軟件包），完成所有的配置。Debian/Ubuntu使用的apt-get，Fedora/CentOS使用的yum，以及OSX下可用的homebrew都是優秀的軟件包管理器。

你決定設計你自己的軟件包管理器。不可避免地，你要解決軟件包之間的依賴問題。如果軟件包A依賴軟件包B，那么安裝軟件包A以前，必須先安裝軟件包B。同時，如果想要卸載軟件包B，則必須卸載軟件包A。現在你已經獲得了所有的軟件包之間的依賴關系。而且，由于你之前的工作，除0號軟件包以外，在你的管理器當中的軟件包都會依賴一個且僅一個軟件包，而0號軟件包不依賴任何一個軟件包。依賴關系不存在環（若有m(m≥2)個軟件包A1,A2,A3,?,Am，其中A1依賴A2，A2依賴A3，A3依賴A4，……，A[m-1]依賴Am，而Am依賴A1，則稱這m個軟件包的依賴關系構成環），當然也不會有一個軟件包依賴自己。

現在你要為你的軟件包管理器寫一個依賴解決程序。根據反饋，用戶希望在安裝和卸載某個軟件包時，快速地知道這個操作實際上會改變多少個軟件包的安裝狀態（即安裝操作會安裝多少個未安裝的軟件包，或卸載操作會卸載多少個已安裝的軟件包），你的任務就是實現這個部分。注意，安裝一個已安裝的軟件包，或卸載一個未安裝的軟件包，都不會改變任何軟件包的安裝狀態，即在此情況下，改變安裝狀態的軟件包數為0。

輸入格式
輸入文件的第1行包含1個整數n，表示軟件包的總數。軟件包從0開始編號。
隨后一行包含n?1個整數，相鄰整數之間用單個空格隔開，分別表示1,2,3,?,n?2,n?1號軟件包依賴的軟件包的編號。

接下來一行包含1個整數q，表示詢問的總數。之后q行，每行1個詢問。詢問分為兩種：
install x：表示安裝軟件包x
uninstall x：表示卸載軟件包x

你需要維護每個軟件包的安裝狀態，一開始所有的軟件包都處于未安裝狀態。
對于每個操作，你需要輸出這步操作會改變多少個軟件包的安裝狀態，隨后應用這個操作（即改變你維護的安裝狀態）。

輸出格式
輸出文件包括q行。
輸出文件的第i行輸出1個整數，為第i步操作中改變安裝狀態的軟件包數。

輸入輸出樣例
輸入
7
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 0
輸出
3
1
3
2
3

輸入
10
0 1 2 1 3 0 0 3 2
10
install 0
install 3
uninstall 2
install 7
install 5
install 9
uninstall 9
install 4
install 1
install 9
輸出
1
3
2
1
3
1
1
1
0
1
說明/提示
【樣例說明 1】
一開始所有的軟件包都處于未安裝狀態。
安裝5號軟件包，需要安裝0,1,5三個軟件包。
之后安裝6號軟件包，只需要安裝6號軟件包。此時安裝了0,1,5,6四個軟件包。
卸載1號軟件包需要卸載1,5,6三個軟件包。此時只有0號軟件包還處于安裝狀態。
之后安裝4號軟件包，需要安裝1,4兩個軟件包。此時0,1,4處在安裝狀態。最后，卸載0號軟件包會卸載所有的軟件包。`

【數據范圍】

題解

這就是一個樹鏈剖分模板題：
但是怎么感覺跟模板有一丟丟不太一樣的感jio呢

每個$i$有且只有一個依附，也就是只會有一個爸爸，加上題目保證不會有環，那么這肯定是一棵樹了！

安裝時要從$i$往上找每一個的依賴安裝包，直到根節點$0$為止，可以用模板往上找。

卸載時要從$i$往下開始把每一個依賴i的安裝包或者間接依賴I的安裝包都刪掉，直到葉子結點
即，刪掉$i$（包含$i$）的子樹

這中間的計算再用線段樹維護，更改即可，還可以優美的打個$lazy$懶標記

代碼實現

#include <cstdio> #include <vector> using namespace std; #define MAXN 100005 int tree[MAXN << 2]; int sum[MAXN << 2]; vector < int > G[MAXN]; int n, q, x, cnt; char s[10]; int f[MAXN], id[MAXN], dep[MAXN], tot[MAXN], son[MAXN], top[MAXN];void dfs1 ( int u, int fa, int depth ) {dep[u] = depth;tot[u] = 1;for ( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i];if ( v == fa ) continue;dfs1 ( v, u, depth + 1 );tot[u] += tot[v];if ( tot[v] > tot[son[u]] || ! son[u] )son[u] = v;} }void dfs2 ( int u, int t ) {id[u] = ++ cnt;top[u] = t;if ( ! son[u] ) return;dfs2 ( son[u], t );for ( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i];if ( v == son[u] || v == f[u] ) continue;dfs2 ( v, v );} }void pushdown ( int l, int r, int num ) {if ( sum[num] == 0 )sum[num << 1] = sum[num << 1 | 1] = 0;if ( sum[num] == r - l + 1 ) {int mid = ( l + r ) >> 1;sum[num << 1] = mid - l + 1;sum[num << 1 | 1] = r - mid;} }void update ( int l, int r, int L, int R, int num, bool opt ) {if ( L <= l && r <= R ) {sum[num] = ( r - l + 1 ) * opt;return;}int mid = ( l + r ) >> 1;if ( L <= mid ) update ( l, mid, L, R, num << 1, opt );if ( mid < R ) update ( mid + 1, r, L, R, num << 1 | 1, opt );sum[num] = sum[num << 1] + sum[num << 1 | 1]; }int query ( int l, int r, int L, int R, int num ) {if ( L <= l && r <= R ) return sum[num];pushdown ( l, r, num );int mid = ( l + r ) >> 1;int sum1 = 0, sum2 = 0;if ( L <= mid ) sum1 = query ( l, mid, L, R, num << 1 );if ( mid < R ) sum2 = query ( mid + 1, r, L, R, num << 1 | 1 );return sum1 + sum2; }void solve_sum ( int x ) {int ans = 0, fx = top[x];while ( fx ) {ans += id[x] - id[fx] - query ( 0, cnt, id[fx], id[x], 1 ) + 1;update ( 0, cnt, id[fx], id[x], 1, 1 );x = f[fx];fx = top[x];}ans += id[x] - id[0] - query ( 0, cnt, id[fx], id[x], 1 ) + 1;update ( 0, cnt, id[0], id[x], 1, 1 );printf ( "%d\n", ans ); }int main() {scanf ( "%d", &n );for ( int i = 1;i < n;i ++ ) {scanf ( "%d", &f[i] );G[f[i]].push_back ( i );}dfs1 ( 0, -1, 1 );dfs2 ( 0, 0 );scanf ( "%d", &q ); for ( int i = 1;i <= q;i ++ ) {scanf ( "\n%s %d", s, &x );if ( s[0] == 'i' )solve_sum ( x );else {printf ( "%d\n", query ( 0, cnt, id[x], id[x] + tot[x] - 1, 1 ) );update ( 0, cnt, id[x], id[x] + tot[x] - 1, 1, 0 ); }}return 0; }

不如趁熱打鐵：
再來一道例題吧~(づ￣3￣)づ╭?～

例題2：POJ3237 tree

題目

給你由N個結點組成的樹。樹的節點被編號為1到N，邊被編號為1到N-1。每一條邊有一個權值。然后你要在樹上執行一系列指令。指令可以是如下三種之一：

CHANGE i v：將第i條邊的權值改成v。
NEGATE a b：將點a到點b路徑上所有邊的權值變成其相反數。
QUERY a b：找出點a到點b路徑上各邊的最大權值。

輸入格式
輸入文件的第一行有一個整數N（N<=10000）。
接下來N-1行每行有三個整數a,b,c，代表點a和點b之間有一條權值為c的邊。這些邊按照其編號從小到大給出。
接下來是若干條指令（不超過10^5條），都按照上面所說的格式。
輸入文件的最后一行是"DONE".
輸出格式
對每個“QUERY”指令，輸出一行，即路徑上各邊的最大權值。

樣例
input1
3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
output1
1
3

input2
5
2 1 8
1 3 4
4 1 3
5 3 7
NEGATE 1 4
CHANGE 1 9
NEGATE 2 1
CHANGE 1 9
NEGATE 5 1
NEGATE 2 1
QUERY 5 1
QUERY 3 1
CHANGE 3 6
NEGATE 3 1
DONE
output2
-4
-4

數據范圍與提示
N <= 10000

題解

首先這道題可以發現以任何一個點作為根節點都不會影響這棵樹的長相
我們就老規矩以1作為根節點建樹

其次這道題不同于模板的就是這是一個邊權的樹鏈剖分
那我們就要把邊權變為我們的模板

因為這道題我完全是自己做的，

---

所以我的思路是把邊權塞成點權
具體操作如下：
因為這是一棵樹那么每一個點的爸爸都只有$1$個，
所以我就考慮把這條邊的邊權塞給兒子$v$節點的點權，
這樣接下來的操作完全就是線段樹模板+樹鏈模板

然后這道題有取相反數的操作，也就意味著原本的最小值有可能咸魚翻身變成最大值
這就提醒我們線段樹要開成結構體，存下$max$和$min$

但是這道題既然把邊權塞成了點權，就要考慮一些情況：

1）：我們線段樹的范圍是$[1,cnt]$，包含了根節點$1$，
而我們把邊塞成了點，自然根節點$1$是不應該被算的，
所以我們可以把根節點$1$的線段樹區間的最小值置為極大值INF，最大值置為極小值-INF
這樣在比對最大值和最小值往上傳給父親區間的時候，我們就能保證不選根節點$1$的區間

2）：當我們找答案$x,y$，爬到了同一個重鏈的時候，要注意：
我們以$id[x]<=id[y]$為例，當他們爬到同一個重鏈的時候，$id[x]$的值代表了$x$和$x$爸爸這條邊的值
很明顯我們只需要$xy$包含的邊值，就要把這條邊給排除掉
這時只需要$id[x]+1$就可以避免了

還不理解我們就用圖來表示：

我們現在求的是$x?y$的邊中最大值，也就是$j$和$k$兩條邊的最大值
上面提過把邊權塞給兒子節點，
那么$x$的點權$id[x]$也就是$fxx$這條邊的邊權，即$i$
我們如果按照模板的打法$L，R$傳的就是$id[x],id[y]$，這樣我們就多算了一條$i$
所以我們才要進行$id[x+1]$，把這條邊排除掉

會不會存在$id[x]+1>id[y]$的情況呢？

最簡單的就是$x$是$y$的直系爸爸
那么$id[x]+1$就剛好是$id[y]$，$id[y]$的點權存的又是$xy$兩點之間的邊權，剛好就是我們想要的

然后這道題就這么結束了。。。

代碼實現

添加鏈接描述

#include <cstdio> #include <vector> #include <iostream> using namespace std; #define inf 0x7f7f7f7f #define maxn 10005 #define lson now << 1 #define rson now << 1 | 1 pair < int, int > edge[maxn]; struct node { int to, w; }; vector < node > G[maxn]; int T, n, cnt; int dep[maxn], f[maxn], siz[maxn], val[maxn], son[maxn]; int id[maxn], dfn[maxn], top[maxn]; int Max[maxn << 2], Min[maxn << 2]; bool tag[maxn << 2];void dfs1( int u, int fa ) {dep[u] = dep[fa] + 1, f[u] = fa, siz[u] = 1;for( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i].to, w = G[u][i].w;if( v == fa ) continue;else dfs1( v, u );val[v] = w;siz[u] += siz[v];if( ! son[u] or siz[v] > siz[son[u]] ) son[u] = v;} }void dfs2( int u, int t ) {top[u] = t, dfn[u] = ++ cnt, id[cnt] = u;if( ! son[u] ) return;else dfs2( son[u], t );for( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i].to;if( v == f[u] or v == son[u] ) continue;else dfs2( v, v );} }void build( int now, int l, int r ) {tag[now] = 0;if( l == r ) { if( l ^ 1 ) Max[now] = Min[now] = val[id[l]];else Max[now] = -inf, Min[now] = inf;return;}int mid = ( l + r ) >> 1;build( lson, l, mid );build( rson, mid + 1, r );Max[now] = max( Max[lson], Max[rson] );Min[now] = min( Min[lson], Min[rson] ); }void modify( int now ) {Max[now] = -Max[now];Min[now] = -Min[now];swap( Max[now], Min[now] );tag[now] ^= 1; }void pushdown( int now ) {if( ! tag[now] ) return;modify( lson );modify( rson );tag[now] = 0; }void modify( int now, int l, int r, int pos, int v ) {if( l == r ) { Max[now] = Min[now] = v; return; }pushdown( now );int mid = ( l + r ) >> 1;if( pos <= mid ) modify( lson, l, mid, pos, v );else modify( rson, mid + 1, r, pos, v );Max[now] = max( Max[lson], Max[rson] );Min[now] = min( Min[lson], Min[rson] ); }void reverse( int now, int l, int r, int L, int R ) {if( R < l or r < L or L > R ) return;if( L <= l and r <= R ) { modify( now ); return; }pushdown( now );int mid = ( l + r ) >> 1;reverse( lson, l, mid, L, R );reverse( rson, mid + 1, r, L, R );Max[now] = max( Max[lson], Max[rson] );Min[now] = min( Min[lson], Min[rson] ); }void reverse( int x, int y ) {while( top[x] ^ top[y] ) {if( dep[x] < dep[y] ) swap( x, y );reverse( 1, 1, n, dfn[top[x]], dfn[x] );x = f[top[x]];}if( dep[x] > dep[y] ) swap( x, y );reverse( 1, 1, n, dfn[x] + 1, dfn[y] ); }int query( int now, int l, int r, int L, int R ) {if( r < L or R < l or L > R ) return -inf;if( L <= l and r <= R ) return Max[now];pushdown( now );int mid = ( l + r ) >> 1;return max( query( lson, l, mid, L, R ), query( rson, mid + 1, r, L, R ) ); }void query( int x, int y ) {int ans = -inf;while( top[x] ^ top[y] ) {if( dep[top[x]] < dep[top[y]] ) swap( x, y );ans = max( ans, query( 1, 1, n, dfn[top[x]], dfn[x] ) );x = f[top[x]];}if( dep[x] > dep[y] ) swap( x, y );ans = max( ans, query( 1, 1, n, dfn[x] + 1, dfn[y] ) );printf( "%d\n", ans ); }int main() {scanf( "%d", &T );while( T -- ) {scanf( "%d", &n );cnt = 0;for( int i = 1;i <= n;i ++ ) G[i].clear(), son[i] = 0;for( int i = 1, u, v, w;i < n;i ++ ) {scanf( "%d %d %d", &u, &v, &w );edge[i] = make_pair( u, v );G[u].push_back( { v, w } );G[v].push_back( { u, w } );}dfs1( 1, 0 );dfs2( 1, 1 );build( 1, 1, n );char opt[10]; int a, b;while( 1 ) {scanf( "%s", opt );if( opt[0] == 'D' ) break;else {scanf( "%d %d", &a, &b );switch( opt[0] ) {case 'C' : {if( dep[edge[a].first] < dep[edge[a].second] )modify( 1, 1, n, dfn[edge[a].second], b );elsemodify( 1, 1, n, dfn[edge[a].first], b );break;}case 'N' : reverse( a, b ); break;case 'Q' : query( a, b ); break;}}}}return 0; }

好了，樹鏈剖分就到這里了

總結

以上是生活随笔為你收集整理的树链剖分概念及模板 + 例题 [POJ3237 tree + 软件包管理器]的全部內容，希望文章能夠幫你解決所遇到的問題。

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