[C++]樹鏈剖分
預備知識
- 樹的基礎知識
- 關于這個本文有介紹
- 鄰接表存圖
- 線段樹基礎
- 會區間加法和區間結合就可以了P3372
- 建議閱讀這篇Blog
- 最近公共祖先LCA
- 雖然用不到這個思想 但是有類似的
- 有助于快速理解代碼
- 建議閱讀這篇Blog
題意解讀
題目描述
如題，已知一棵包含 \(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\) 為根節點的子樹內所有節點值之和
輸入格式
第一行包含 44 個正整數 N,M,R,P，分別表示樹的結點個數、操作個數、根節點序號和取模數（即所有的輸出結果均對此取模），
接下來一行包含 N 個非負整數，分別依次表示各個節點上初始的數值，
接下來 N-1 行每行包含兩個整數 x,y，表示點 x 和點 y 之間連有一條邊（保證無環且連通），
接下來 MM 行每行包含若干個正整數，每行表示一個操作，格式如下：
操作 1： x y z；
操作 2： x y；
操作 3： x z；
操作 4： x，
輸出格式
輸出包含若干行，分別依次表示每個操作 22 或操作 44 所得的結果（對 PP 取模）
選自洛谷
演算法思想
樹鏈剖分
顧名思義 就是把樹形結構改良成鏈狀結構
這樣可以通過線段樹方便的維護
為了更好的講解
這里先列舉出幾個概念：
- 重兒子 是指當前節點的所有兒子中子樹最大的兒子
- 重鏈 全部由重兒子組成的鏈
接下來要進行的第一步
剖分樹
剖分樹需要有一個標準
這樣才可以準確的知道這個樹形結構是如何剖分的
這個標準就是 重兒子
這樣就能剖出重鏈
將重鏈去掉后
再回圈這個步驟
就能把一棵樹剖成有限個鏈
舉個例子
這樣樹就剖好了
線段樹維護
樹剖只是把樹剖成的鏈條
但是還沒能達到維護資料的目的
這個時候就可以用代碼究極繁瑣但是實用無比的線段樹了
這個時候就需要創造能用線段樹維護的條件了
我們首先先要對這棵樹的節點按照鏈來重新排序號
然后再用線段樹維護
具體方法詳見代碼講解
代碼講解
這里先把變數的含義解釋一下：
#define maxn 200007
#define mid ((l+r)>>1)
#define li i<<1
#define ri 1+(i<<1)
int n,m,root,mod;
//n m如題 root為根節點 mod為取余數
int deep[maxn],father[maxn],son[maxn],sub[maxn];
//deep代表深度 father代表父親節點 son代表重兒子 sub代表子樹的大小
int head[maxn],cnt,value[maxn];
//head cnt均為鄰接表引數 value代表節點權值
//注 這里value是故意不存在鄰接表里的
int top[maxn],id[maxn],value_sort[maxn];
//top 所在鏈的第一個節點 id新排序后的序號 value_sort新排序后的權值
struct Edge{//鄰接表
int u,v;
Edge(int a = 0,int b = 0){
u = head[a];
v = b;
}
}e[maxn << 1];
struct Tree{//線段樹
int l,r,sum;
int lazy;
}t[maxn << 1];
這個代碼一共有個核心的函式
- \(Dfs1\)
- \(Dfs2\)
- 線段樹相關函式
- \(Build\)
- \(push\)
- \(add\)
- \(search\)
- \(search\)_\(tree\)
- \(add\)_\(tree\)
我們依次來看
Dfs1
int dfs1(int u,int fa){
deep[u] = deep[fa] + 1;//u節點的深度比其父親的深度大1
father[u] = fa;//存下u的父親為fa
sub[u] = 1;//子樹大小 先把自己的1給加上
int maxson = -1;//用來判定重兒子
for(int i = head[u];i;i = e[i].u){
int ev = e[i].v;
if(ev == fa) continue;
sub[u] += dfs1(ev,u);//讓子樹大小加上兒子節點的子樹大小
if(sub[ev] > maxson){//若兒子i的子樹大小比以往的都大
maxson = sub[ev];
son[u] = ev;
//那就更新狀態
}
}
return sub[u];//回傳u的樹的大小
}
這是用來求 \(deep\) \(father\) \(son\) \(sub\) 的函式
這部分總體比較簡單
注釋就直接打代碼上了
Dfs2
void dfs2(int u,int topf){
id[u] = ++cnt;
value_sort[cnt] = value[u];
top[u] = topf;
if(!son[u]) return;
dfs2(son[u],topf);
for(int i = head[u];i;i = e[i].u){
int ev = e[i].v;
if(!id[ev])
dfs2(ev,ev);
}
}
這部分是進行剖分
由于重兒子已經得到
那就沿著重兒子進行深搜就行了
注意這里是先進行dfs重兒子的遞回再dfs其余兒子
因為我們是要把這條重鏈先剖出來
這里 \(for\) 回圈里 \(if\) 的條件是：
!id[ev]
這說明這個變數還沒有被賦值過
即還沒有被 \(Dfs\) 到過
這樣再進行深搜
線段樹相關函式
這部分就是完全用了線段樹
不需要改動
唯一注意的就是要加上取模
search_tree
int search_tree(int x,int y){
int ans = 0;
while(top[x] != top[y]){
if(deep[top[x]] < deep[top[y]]) swap(x,y);
ans = (ans + search(1,id[top[x]],id[x])) % mod;
x = father[top[x]];
}
if(deep[x] > deep[y]) swap(x,y);
ans = (ans + search(1,id[x],id[y])) % mod;
return ans;
}
這里的寫法有點類似于LCA的樹上倍增
來個例子：
- \(top[x] != top[y]\)
其代表了 \(x\) 和 \(y\) 不處于一條鏈上的時候
就需要先把他們放到一條鏈上
這里我們對 \(top[x]\) 和 \(top[y]\) 的深度進行比較
讓 \(x\) 處于深層
然后再把這個線段的值加上
注意這里的 \(top[x]\) 和 \(top[y]\) 并不是同一個點
因為 \(top\) 指的是當前鏈的頂端
（這里圖畫的有點小錯誤）
這里重復上述程序
把線段的值加上
這樣 \(x\) \(y\) 兩點間的值就可以得到了
add_tree
void add_tree(int x,int y,int k){
while(top[x] != top[y]){
if(deep[top[x]] < deep[top[y]]) swap(x,y);
add(1,id[top[x]],id[x],k);
x = father[top[x]];
}
if(deep[x] > deep[y]) swap(x,y);
add(1,id[x],id[y],k);
}
這里的思想和 \(search\)_\(tree\) 的思想完全相同
就不再贅述了
吐槽
這個代碼真的長
敲起來超費勁
Code
#include<bits/stdc++.h>
#define maxn 200007
#define mid ((l+r)>>1)
#define li i<<1
#define ri 1+(i<<1)
using namespace std;
int n,m,root,mod;
int deep[maxn],father[maxn],son[maxn],sub[maxn];
int head[maxn],cnt,value[maxn];
int top[maxn],id[maxn],value_sort[maxn];
struct Edge{
int u,v;
Edge(int a = 0,int b = 0){
u = head[a];
v = b;
}
}e[maxn << 1];
struct Tree{
int l,r,sum;
int lazy;
}t[maxn << 1];
void Read(){
int a,b;
cin >> n >> m >> root >> mod;
for(int i = 1;i <= n;i++) cin >> value[i];
for(int i = 1;i < n;i++){
cin >> a >> b;
e[++cnt] = Edge(a,b);
head[a] = cnt;
e[++cnt] = Edge(b,a);
head[b] = cnt;
}
}
int dfs1(int u,int fa){
deep[u] = deep[fa] + 1;
father[u] = fa;
sub[u] = 1;
int maxson = -1;
for(int i = head[u];i;i = e[i].u){
int ev = e[i].v;
if(ev == fa) continue;
sub[u] += dfs1(ev,u);
if(sub[ev] > maxson){
maxson = sub[ev];
son[u] = ev;
}
}
return sub[u];
}
void dfs2(int u,int topf){
id[u] = ++cnt;
value_sort[cnt] = value[u];
top[u] = topf;
if(!son[u]) return;
dfs2(son[u],topf);
for(int i = head[u];i;i = e[i].u){
int ev = e[i].v;
if(!id[ev])
dfs2(ev,ev);
}
}
void Build(int i,int l,int r){
t[i].l = l;
t[i].r = r;
if(l == r){
t[i].sum = value_sort[l];
return ;
}
Build(li,l,mid);
Build(ri,mid+1,r);
t[i].sum = t[li].sum + t[ri].sum;
}
void push(int i){
t[li].lazy = (t[li].lazy + t[i].lazy) % mod;
t[ri].lazy = (t[ri].lazy + t[i].lazy) % mod;
int mid_ = (t[i].l + t[i].r) >> 1;
t[li].sum = (t[li].sum + t[i].lazy * (mid_-t[i].l+1)) % mod;
t[ri].sum = (t[ri].sum + t[i].lazy * (t[i].r - mid_)) % mod;
t[i].lazy = 0;
}
void add(int i,int l,int r,int k){
if(l <= t[i].l && t[i].r <= r){
t[i].sum += k * (t[i].r - t[i].l + 1);
t[i].lazy += k;
return ;
}
if(t[i].lazy != 0) push(i);
if(t[li].r >= l)
add(li,l,r,k);
if(t[ri].l <= r)
add(ri,l,r,k);
t[i].sum = (t[li].sum + t[ri].sum) % mod;
}
int search(int i,int l,int r){
if(l <= t[i].l && t[i].r <= r)
return t[i].sum;
push(i);
int ans = 0;
if(t[li].r >= l) ans = (ans + search(li,l,r)) % mod;
if(t[ri].l <= r) ans = (ans + search(ri,l,r)) % mod;
return ans;
}
int search_tree(int x,int y){
int ans = 0;
while(top[x] != top[y]){
if(deep[top[x]] < deep[top[y]]) swap(x,y);
ans = (ans + search(1,id[top[x]],id[x])) % mod;
x = father[top[x]];
}
if(deep[x] > deep[y]) swap(x,y);
ans = (ans + search(1,id[x],id[y])) % mod;
return ans;
}
void add_tree(int x,int y,int k){
while(top[x] != top[y]){
if(deep[top[x]] < deep[top[y]]) swap(x,y);
add(1,id[top[x]],id[x],k);
x = father[top[x]];
}
if(deep[x] > deep[y]) swap(x,y);
add(1,id[x],id[y],k);
}
void interaction(){
int tot;
int x,y,z;
for(int i = 1;i <= m;i++){
cin >> tot;
if(tot == 1){
cin >> x >> y >> z;
add_tree(x,y,z%mod);
}
if(tot == 2){
cin >> x >> y;
cout << search_tree(x,y)%mod << endl;
}
if(tot == 3){
cin >> x >> z;
add(1,id[x],id[x]+sub[x]-1,z%mod);
}
if(tot == 4){
cin >> x;
cout << search(1,id[x],id[x]+sub[x]-1)%mod << endl;
}
}
}
int main(){
Read();
dfs1(root,0);
cnt = 0;
dfs2(root,root);
Build(1,1,n);
interaction();
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/272750.html
標籤：其他