树链剖分入门
這幾天學(xué)了一個(gè)樹鏈剖分，覺(jué)得還不是很難，這里我試著講一講吧。
?
首先，我認(rèn)為樹鏈剖分是把在樹上一個(gè)節(jié)點(diǎn)一個(gè)節(jié)點(diǎn)的走改為按照某種規(guī)則跳，從而降低了時(shí)間復(fù)雜度。
?
那這是什么規(guī)則呢？
首先我們得知道什么是重鏈，知道什么是重鏈就得先知道什么是重兒子，重兒子就是子樹較大的兒子。然后對(duì)于一個(gè)點(diǎn)，我們總是往他的重兒子走，這樣就構(gòu)成了重鏈，那么剩下的就是輕鏈。
放張圖直觀些
?
然后我們同樣可以對(duì)樹進(jìn)行dfs，只不過(guò)重兒子優(yōu)先，這樣我們也得到了一個(gè)dfs序，于是我們把樹上問(wèn)題成功轉(zhuǎn)化成了線性問(wèn)題。接著就可以用線段樹等數(shù)據(jù)結(jié)構(gòu)維護(hù)了。
?
那就拿這道板子體為例：https://www.luogu.org/problemnew/show/P3384
?
首先是兩遍dfs，第一遍dfs維護(hù)子樹大小size[]，節(jié)點(diǎn)深度dep[]，重兒子son[]，以及一個(gè)節(jié)點(diǎn)的父親節(jié)點(diǎn)（因?yàn)槿绻搅艘粭l鏈的頂端，就要再自己走到他的父親節(jié)點(diǎn)）。
1 void dfs1(int now) 2 { 3 vis[now] = 1; 4 size[now] = 1; 5 for(int i = 0; i < (int)v[now].size(); ++i) 6 { 7 if(!vis[v[now][i]]) 8 { 9 dep[v[now][i]] = dep[now] + 1; 10 fa[v[now][i]] = now; 11 dfs1(v[now][i]); 12 size[now] += size[v[now][i]]; 13 if(!son[now] || size[son[now]] < size[v[now][i]]) son[now] = v[now][i]; 14 //如果沒(méi)有重兒子，或者當(dāng)前子樹大小大于重兒子的子樹大小，就更新重兒子 15 } 16 } 17 }?
第二遍dfs是維護(hù)dfs序dfsx[]，每一條鏈的頂端是哪一個(gè)節(jié)點(diǎn)。但我們還要在維護(hù)一個(gè)pos[]，因?yàn)楫?dāng)我們將樹轉(zhuǎn)化成線性后，用線段樹建樹的時(shí)候需要添加節(jié)點(diǎn)，而這個(gè)節(jié)點(diǎn)的編號(hào)是dfs序的編號(hào)，所以需要再用一個(gè)數(shù)組記錄dfs序的編號(hào)所對(duì)應(yīng)的樹上節(jié)點(diǎn)編號(hào)。
1 int cnt = 0, dfsx[maxn], pos[maxn], top[maxn]; 2 void dfs2(int now) 3 { 4 //dfsx[]因?yàn)橹腔鄹乱淮?#xff0c;所以可以當(dāng)做vis[]用 5 dfsx[now] = ++cnt; pos[cnt] = now; 6 if(son[now]) 7 { 8 top[son[now]] = top[now]; 9 dfs2(son[now]); //優(yōu)先走重兒子，保證一條鏈在dfs序上的編號(hào)是連續(xù)的 10 } 11 for(int i = 0; i < (int)v[now].size(); ++i) 12 { 13 if(!dfsx[v[now][i]] && son[now] != v[now][i]) //再走不是重兒子的節(jié)點(diǎn) 14 { 15 top[v[now][i]] = v[now][i]; //輕兒子所在的鏈只有他自己一個(gè)節(jié)點(diǎn)，所以頂端節(jié)點(diǎn)就是他自己 16 dfs2(v[now][i]); 17 } 18 } 19 }?
這兩個(gè)預(yù)處理完事后就可以看看題了。
?
第一個(gè)詢問(wèn)，將樹從x到y(tǒng)結(jié)點(diǎn)最短路徑上所有節(jié)點(diǎn)的值都加上z。
首先我們要將x，y移到同一條鏈上，具體操作就是如果其中一個(gè)點(diǎn)所在鏈的頂端的深度更低，就將他跳到鏈的頂端，并更新他到頂端節(jié)點(diǎn)的區(qū)間。
移到同一條鏈上后，就更新這兩個(gè)點(diǎn)的區(qū)間就行了
1 void pathUpdate(int x, int y, int z) 2 { 3 while(top[x] != top[y]) //先把這倆搞到一條鏈上 4 { 5 if(dep[top[x]] < dep[top[y]]) swap(x, y); //默認(rèn)讓x跳 6 update(dfsx[top[x]], dfsx[x], 1, z); 7 x = fa[top[x]]; 8 } 9 if(dfsx[x] > dfsx[y]) swap(x, y); 10 update(dfsx[x], dfsx[y], 1, z); 11 }?
操作2： 求樹從x到y(tǒng)結(jié)點(diǎn)最短路徑上所有節(jié)點(diǎn)的值之和
和修改一樣，先把兩點(diǎn)移到同一條鏈上，然后計(jì)算跳的點(diǎn)在該鏈上的貢獻(xiàn)
1 ll pathQuery(int x, int y) 2 { 3 ll ret = 0; 4 while(top[x] != top[y]) 5 { 6 if(dep[top[x]] < dep[top[y]]) swap(x, y); 7 ret += query(dfsx[top[x]], dfsx[x], 1); ret %= mod; 8 x = fa[top[x]]; 9 } 10 if(dfsx[x] > dfsx[y]) swap(x, y); 11 ret += query(dfsx[x], dfsx[y], 1); ret %= mod; 12 return ret; 13 }操作3： 將以x為根節(jié)點(diǎn)的子樹內(nèi)所有節(jié)點(diǎn)值都加上z
值得一提的是，盡管我們?cè)诰S護(hù)dfs序時(shí)是重鏈優(yōu)先遍歷，但仍滿足一個(gè)節(jié)點(diǎn)以及他的子樹在dfs序上是一段長(zhǎng)為子樹大小的連續(xù)區(qū)間，自己畫一畫就明白了
這里和查詢放一塊
1 void sbtUpdate(int x, int z) 2 { 3 update(dfsx[x], dfsx[x] + size[x] - 1, 1, z); 4 } 5 ll sbtQuery(int x) 6 { 7 return query(dfsx[x], dfsx[x] + size[x] - 1, 1); 8 }?
這樣板子就寫完了，是不是很簡(jiǎn)單？
然后最重要的一件事是別忘了取模，而且每一個(gè)運(yùn)算后都要取，否則你就可能70分代碼debug一小時(shí)……
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<vector> 7 #include<cctype> 8 using namespace std; 9 #define enter printf("\n") 10 #define space printf(" ") 11 typedef long long ll; 12 const int INF = 0x3f3f3f3f; 13 const int maxn = 1e5 + 5; 14 inline ll read() 15 { 16 ll ans = 0; 17 char ch = getchar(), last = ' '; 18 while(!isdigit(ch)) {last = ch; ch = getchar();} 19 while(isdigit(ch)) 20 { 21 ans = ans * 10 + ch - '0'; ch = getchar(); 22 } 23 if(last == '-') ans = -ans; 24 return ans; 25 } 26 inline void write(ll x) 27 { 28 if(x < 0) x = -x, putchar('-'); 29 if(x >= 10) write(x / 10); 30 putchar('0' + x % 10); 31 } 32 33 int n, m, s, mod; 34 int a[maxn]; 35 vector<int> v[maxn]; 36 37 bool vis[maxn]; 38 int fa[maxn], son[maxn], size[maxn], dep[maxn]; 39 void dfs1(int now) 40 { 41 vis[now] = 1; 42 size[now] = 1; 43 for(int i = 0; i < (int)v[now].size(); ++i) 44 { 45 if(!vis[v[now][i]]) 46 { 47 dep[v[now][i]] = dep[now] + 1; 48 fa[v[now][i]] = now; 49 dfs1(v[now][i]); 50 size[now] += size[v[now][i]]; 51 if(!son[now] || size[son[now]] < size[v[now][i]]) son[now] = v[now][i]; 52 //如果沒(méi)有重兒子，或者當(dāng)前子樹大小大于重兒子的子樹大小，就更新重兒子 53 } 54 } 55 } 56 //第二遍dfs是維護(hù)dfs序dfsx[]，每一條鏈的頂端是哪一個(gè)節(jié)點(diǎn) 57 58 int cnt = 0, dfsx[maxn], pos[maxn], top[maxn]; 59 void dfs2(int now) 60 { 61 //dfsx[]因?yàn)橹腔鄹乱淮?#xff0c;所以可以當(dāng)做vis[]用 62 dfsx[now] = ++cnt; pos[cnt] = now; 63 if(son[now]) 64 { 65 top[son[now]] = top[now]; 66 dfs2(son[now]); //優(yōu)先走重兒子，保證一條鏈在dfs序上的編號(hào)是連續(xù)的 67 } 68 for(int i = 0; i < (int)v[now].size(); ++i) 69 { 70 if(!dfsx[v[now][i]] && son[now] != v[now][i]) //再走不是重兒子的節(jié)點(diǎn) 71 { 72 top[v[now][i]] = v[now][i]; //輕兒子所在的鏈只有他自己一個(gè)節(jié)點(diǎn)，所以頂端節(jié)點(diǎn)就是他自己 73 dfs2(v[now][i]); 74 } 75 } 76 } 77 78 int l[maxn << 2], r[maxn << 2]; 79 ll sum[maxn << 2], lazy[maxn << 2]; 80 void build(int L, int R, int now) 81 { 82 l[now] = L; r[now] = R; 83 if(L == R) {sum[now] = a[pos[L]]; return;} 84 int mid = (L + R) >> 1; 85 build(L, mid, now << 1); 86 build(mid + 1, R, now << 1 | 1); 87 sum[now] = (sum[now << 1] + sum[now << 1 | 1]) % mod; 88 } 89 void pushdown(int now) 90 { 91 if(lazy[now]) 92 { 93 lazy[now << 1] += lazy[now]; lazy[now << 1] %= mod; 94 lazy[now << 1 | 1] += lazy[now]; lazy[now << 1 | 1] %= mod; 95 sum[now << 1] += (ll)(r[now << 1] - l[now << 1] + 1) * lazy[now]; sum[now << 1] %= mod; 96 sum[now << 1 | 1] += (ll)(r[now << 1 | 1] - l[now << 1 | 1] + 1) * lazy[now]; sum[now << 1 | 1] %= mod; 97 lazy[now] = 0; 98 } 99 } 100 void update(int L, int R, int now, int d) 101 { 102 if(L == l[now] && R == r[now]) 103 { 104 sum[now] += (ll)(r[now] - l[now] + 1) * d; sum[now] %= mod; 105 lazy[now] += d; lazy[now] %= mod; 106 return; 107 } 108 pushdown(now); 109 int mid = (l[now] + r[now]) >> 1; 110 if(R <= mid) update(L, R, now << 1, d); 111 else if(L > mid) update(L, R, now << 1 | 1, d); 112 else {update(L, mid, now << 1, d); update(mid + 1, R, now << 1 | 1, d);} 113 sum[now] = sum[now << 1] + sum[now << 1 | 1]; 114 } 115 ll query(int L, int R, int now) 116 { 117 if(L == l[now] && R == r[now]) return sum[now]; 118 pushdown(now); 119 int mid = (l[now] + r[now]) >> 1; 120 if(R <= mid) return query(L, R, now << 1); 121 else if(L > mid) return query(L, R, now << 1 | 1); 122 else return (query(L, mid, now << 1) + query(mid + 1, R, now << 1 | 1)) % mod; 123 } 124 125 void pathUpdate(int x, int y, int z) 126 { 127 while(top[x] != top[y]) //先把這倆搞到一條鏈上 128 { 129 if(dep[top[x]] < dep[top[y]]) swap(x, y); //默認(rèn)讓x跳 130 update(dfsx[top[x]], dfsx[x], 1, z); 131 x = fa[top[x]]; 132 } 133 if(dfsx[x] > dfsx[y]) swap(x, y); 134 update(dfsx[x], dfsx[y], 1, z); 135 } 136 ll pathQuery(int x, int y) 137 { 138 ll ret = 0; 139 while(top[x] != top[y]) 140 { 141 if(dep[top[x]] < dep[top[y]]) swap(x, y); 142 ret += query(dfsx[top[x]], dfsx[x], 1); ret %= mod; 143 x = fa[top[x]]; 144 } 145 if(dfsx[x] > dfsx[y]) swap(x, y); 146 ret += query(dfsx[x], dfsx[y], 1); ret %= mod; 147 return ret; 148 } 149 150 void sbtUpdate(int x, int z) 151 { 152 update(dfsx[x], dfsx[x] + size[x] - 1, 1, z); 153 } 154 ll sbtQuery(int x) 155 { 156 return query(dfsx[x], dfsx[x] + size[x] - 1, 1); 157 } 158 159 int main() 160 { 161 n = read(); m = read(); s = read(); mod = read(); 162 for(int i = 1; i <= n; ++i) a[i] = read(); 163 for(int i = 1 ; i < n; ++i) 164 { 165 int a = read(), b = read(); 166 v[a].push_back(b); v[b].push_back(a); 167 } 168 dfs1(s); 169 top[s] = s; dfs2(s); 170 build(1, n, 1); 171 for(int i = 1; i <= m ; ++i) 172 { 173 int d = read(); 174 if(d == 1) 175 { 176 int x = read(), y = read(), z = read(); 177 pathUpdate(x, y, z); 178 } 179 else if(d == 2) 180 { 181 int x = read(), y = read(); 182 write(pathQuery(x, y)); enter; 183 } 184 else if(d == 3) 185 { 186 int x = read(), z = read(); 187 sbtUpdate(x, z); 188 } 189 else 190 { 191 int x = read(); 192 write(sbtQuery(x)); enter; 193 } 194 } 195 return 0; 196 }?
轉(zhuǎn)載于:https://www.cnblogs.com/mrclr/p/9375402.html
總結(jié)
- 上一篇： margin的简单应用
- 下一篇： JAVA自学笔记08