---
tags: 校內培訓 MDCPP
author: LittlePants
title: 競程進階樹論
---
# 樹
樹雖然是相對簡單的圖論，但也因此有了許多自己獨特的性質和有趣的算法。
這邊就不再贅述樹的性質了。
---
## 樹性質的運用
這種題目太多了，這邊舉幾個單純善用樹的性質就能解的題目。
1. [Three Paths on a Tree](https://codeforces.com/problemset/problem/1294/F)
2. [MEX Tree](https://codeforces.com/problemset/problem/1527/D)
3. [Trees of Tranquillity](https://codeforces.com/contest/1529/problem/E)
4. [Even Outdegree Edges](https://cses.fi/problemset/task/2179)
::: spoiler Hint
這題比較難，可以參考這篇[DFS Tree CF blog](https://codeforces.com/blog/entry/68138)
:::
---
## 樹壓平
樹壓平是利用DFS順序的特性把樹壓成一個序列，在這個序列中**每個節點 $x$ 和其子樹節點都會相連**，因此我們就可以利用這個性質對這個序列使用資料結構或其他演算法做到**子樹修改**。
那要怎麼求樹壓平的這個序列呢?
只要在DFS時，每碰到一個新的點就加進序列。
```cpp=
int timer;
void dfs(int now, int pa) {
pos[now] = ++timer;
sz[now] = 1;
for (int v : g[now]) {
if (v == pa) continue;
dfs(v, now);
sz[now] += sz[v];
}
}
```
現在我們只需要再知道每個子樹大小，就可以知道每個子樹區間了。
因為一個節點 $x$ 一定比他的子樹都還要早被放進序列。
所以 $x$ 的子樹區間就是 $[pos[x], \ pos[x] + sz[x] - 1]$
有另一種方式是紀錄每個點進入和離開的時間，其實和上面的差不多，所以就不多解釋了，直接看code。
```cpp=
int timer;
void dfs(int now, int pa) {
st[now] = ++timer;
for (int v : g[now]) {
if (v == pa) continue;
dfs(v, now);
}
ed[now] = timer;
}
```
這樣 $x$ 的子樹區間就是 $[st[x], \ ed[x]]$。
### 練習
1. [Subtree Queries](https://cses.fi/problemset/task/1137)
2. [Path Queries](https://cses.fi/problemset/task/1138)
剛剛發現我只寫過裸題QWQ，之後再補題目好了。
### 題外話
如果有需要對相鄰的節點做操作的題目，可以考慮用BFS序，~~雖然我是沒看過這種題目~~。
---
## LCA 最低公共祖先
LCA應該算是樹的基礎，之後教的東西多多少少多會和它有點關係。
因為我不打算從頭開始教，所以請大家先去看如何用倍增法求出LCA和其他基本應用。
[補充資料 : CPH LCA](https://usaco.guide/CPH.pdf#page=177)
[補充資料 : 倍增法](https://cp-algorithms.com/graph/lca_binary_lifting.html)
### Tarjan LCA
這是我最喜歡寫的LCA求法，因為非常好寫而且很巧妙。
Tarjan真的把DFS發揮到了極致，這個算法只需要用DFS加上並查集就可以做到 $O(N + Q)$ 預處理，$O(1)$ 回答的離線LCA算法。
**注意** : 這裡的雜度沒有反阿克曼函數不是因為我把它當常數省略，是因為用法特殊所以並查集的複雜度是線性。
DFS的流程是這樣 :
1. 往下DFS
2. 處理有關這個點的詢問
3. 將這個點的並查集向父親合併
4. 將這個節點標示為已處理完
上面的處理是怎麼處理呢?
其實也很簡單，如果我們的查詢是 $(a, b)$
那我們到 $a$ 的時候會檢查 $b$，到 $b$ 的時候會檢查 $a$
其中一定會有一個點先到，我們只會在經過第二個點時紀錄答案
紀錄答案也很簡單，就是先到的那個節點的並查集的根節點
我先上個自己的模板
::: spoiler Tarjan 模板
```cpp=
int n, m, dsu[mxN], lca[mxN], eu[mxN], ev[mxN];
vector<int> g[mxN], q[mxN];
bitset<mxN> vis;
inline void dsu_init(int sz) {
for (int i = 0; i <= sz; i++) dsu[i] = i;
}
int get(int x) {
return x == dsu[x] ? x : dsu[x] = get(dsu[x]);
}
void dfs(int u, int p = -1) {
for(int v : g[u]) if(v != p) dfs(v, u); // 往下DFS
// 處理查詢
for(int i : q[u]) {
// i 為詢問編號
int v = u ^ eu[i] ^ ev[i];
// v 為第i比詢問的兩個節點eu[i], ev[i]中 不等於現在所在節點u的那個
if(vis[v]) lca[i] = get(v);
if (v == u) lca[v] = u;
}
vis[u] = 1; // 標示為已完成
dsu[u] = p; // 將並查集向父親節點合併
}
```
:::
<br>
為甚麼這樣會對呢?
可以仔細想一下DFS的流程
如果要查詢 $(a, b)$
可以先不失一般性的假設DFS時會先經過 $a$ 再經過 $b$
DFS時經過 $a$ 後，必定會退到 $a, b$ 的 LCA 才會再經過 $b$
### LCA 轉 RMQ
這個算法用了另一種樹壓平的方式(有人稱為歐拉序?)的方式，用一次DFS將LCA問題轉化成RMQ，所以就可以使用稀疏表(Sparse Table)，做到 $O(N \log N)$預處理，$O(1)$查詢的LCA。
這個方法求出確切的LCA會很麻煩，但如果只求出LCA的深度的話會好寫很多，所以我通常只用在，需要查詢樹上任兩點距離的題目。
這個歐拉序要怎麼求呢?其實也只需要對DFS稍作修改
每**碰到**一個節點就把他加入序列，不管是進入或回退都算
好像有點抽象，所以直接上code和圖
```cpp=
void euler_dfs(int u, int p) {
pos[u] = tp; // 紀錄 u 第一次出現的位置
st[tp++][0] = dep[u]; // 直接放入 st 表
for (int v : g[u]) {
if (v == p) continue;
dep[v] = dep[u] + 1;
euler_dfs(v, u);
st[tp++][0] = dep[u]; // 回退時也要
}
}
```
因為我只是要求距離所以直接紀錄深度
如果要求出LCA是哪個點的話還需要紀錄節點編號 建st表的時候也比較麻煩
這樣看起來好像有點暴力?但其實這個序列只會有 $2n - 1$ 個點
證明其實蠻簡單的可以自己想看看
::: spoiler 證明
每條邊會從兩個方向經過一次，所以每條邊會使兩個點放入序列
根節點第一次拜訪時會直接放入序列
所以序列長度就是 $(N - 1) * 2 + 1$
:::
<br>
那要怎麼查詢呢?
如果要查詢 $(a, b)$ 的 LCA
就只要找到序列中 從 $[min(pos[a], pos[b]), \ max(pos[a], pos[b])]$ 深度最小的點就好了
這個算法為甚麼會對可以用和Tarjan一樣的方式去想，都是因為DFS的特性
這邊附上完整的模板
:::spoiler Euler Sequence LCA
```cpp=
int st[mxN * 2][22], pos[mxN], dep[mxN], tp;
vector<int> g[mxN];
inline void build() {
for(int i = 0; (1<<i) < tp; i++) {
for(int j = 0; j + (1<<i) - 1 < tp; j++) {
st[j][i + 1] = min(st[j][i], st[j + (1<<i)][i]);
}
}
}
inline int query(int l, int r) {
int k = __lg(r - l + 1);
return min(st[l][k], st[r - (1<<k) + 1][k]);
}
inline int dis(int u, int v) {
if (pos[u] > pos[v]) swap(u, v);
return dep[u] + dep[v] - 2 * query(pos[u], pos[v]);
}
void euler_dfs(int u, int p) {
pos[u] = tp;
st[tp++][0] = dep[u];
for (int v : g[u]) {
if (v == p) continue;
dep[v] = dep[u] + 1;
euler_dfs(v, u);
st[tp++][0] = dep[u];
}
}
```
:::
### [例題 Counting Paths](https://cses.fi/problemset/task/1136)
**題目大意**
給你一棵 $N$ 個節點的樹和 $M$ 個路徑，你要把每條路徑上的每個點點權都 +1，最後輸出每個點的點權。
**解法**
如果你會樹練剖分的話，可能會想要直接砸下去，但這題沒有要強制在線，所以其實有更好的做法。
對於一條 $a$ 到 $b$ 的路徑，假設 $l$ 為 $a, b$ 的 LCA ，我們可以把它拆成 $a$ 到 $l$ 和 $l$ 到 $b$
這樣子就好處理很多了，我們可以分別在 $a, b$ 都打上 `+1` 標記，在他麼的 LCA 打上 `-1` 的標記，最後從葉子節點往上做前綴和。
這個技巧好像叫做樹上差分吧?
**圖**
所以我們只需要求 LCA 然後打上標記，最後再做一次 DFS 或 BFS就可以了，如果用 Tarjan 的話就可以做到線性，Tarjan珍香。
### 練習
1. [Root LCA Queries](https://csacademy.com/contest/archive/task/root-lca-queries/statement/)
2. [Gold Transfer](https://codeforces.com/contest/1535/problem/E)
3. [Hot and Cold](https://dmoj.ca/problem/bts17p7)
4. [New Barn](http://www.usaco.org/index.php?page=viewproblem2&cpid=817)
5. [經典題 次小生成樹](https://tioj.ck.tp.edu.tw/problems/1445)
6. [突變史萊姆](https://tioj.ck.tp.edu.tw/problems/1340)
---
## 樹上啟發式
聽起來狠厲害，其實就是在樹上做啟發式合併。
直接來看例題
### [例題 Distinct Colors](https://cses.fi/problemset/task/1139/)
**題目大意**
給定一棵 $N$ 個節點的樹，每個節點上有一個顏色，查詢每個子樹中的相異元素個數
如果會做 **區間元素相異各數** 的人，可以吧他樹壓平直接做。
也可以用樹上莫隊輾過去，但這邊要講一個很好寫的用set就能做出來的方法。
第一點是記憶體，如果對每個點都開set的話一定會TLE，所以可以考慮滾動或每次合併玩就把沒用的set清空。
第二就是要使用啟發式合併，如果用STL的話可以直接swap，因為STL的swap是 $O(1)$ 的。
```cpp=
set<int> dfs(int u, int p){
set<int> t;
t.insert(col[u]);
for(int v : g[u]) {
if(v != p){
s = dfs(v, u);
if(s.size() > t.size()) swap(s,t);
t.insert(s.begin(), s.end());
}
}
ans[u] = t.size();
return t;
}
```
寫起來也很輕鬆，但這樣複雜度是 $O(N \log^2N)$，因為啟發式合併使合併次數變為 $O(N \log N)$，而每次合併都是 $O(\log N)$。
但是有些題目是不能直接使用swap的，這其實也不是太大的問題。
我們只要每次都先往**重子節點**走就沒問題了。
**重子節點**就是子節點中子樹大小最大的，如果有多個最大，就隨便選一個。
對於每個節點，我們都先往重子節點走，並把set初始為記錄重子節點子樹資訊的set。
這樣就可以將上面的程式碼改進。
先假設我們已經把子樹大小都求出來了，並用 $sz[u]$ 代表 $u$ 的子樹大小。
```cpp=
set<int> dfs(int u,int p){
int bson = 0;
for (int v : g[u]) {
if (v != p and sz[bson] < sz[v]) bson = v;
}
set<int> t = dfs(bson, u);
for(int v : g[u]) {
if(v != p and v != bson){
s = dfs(v, u);
t.insert(s.begin(), s.end());
}
}
t.insert(col[u]);
ans[u] = t.size();
return t;
}
```
這時你可能已經發現，我們好像沒有使用set或其他資料結構的必要。
我們可以使用一個陣列和一個變數紀錄每個顏色的出現各數和現在的相異顏色數量。
之後做DFS分為兩種，一種是結束後會清空目前資料的另一種是不清空的。
這邊用 DFS(0)表示會清空的，DFS(1)表示不清空的。
第一次呼叫從根節點開始的DFS時要用DFS(0)或DFS(1)都可以。
我們先定義一下輕子節點，其實就是不是重子節點的子節點都是輕子節點。
對於每個點 $u$，我們依序執行下列步驟。
1. 對 $u$ 的輕子節點**們**點跑DFS(0)
2. 對 $u$ 的重子節點跑DFS(1)，因為資料不會被清空，所以等下可以繼續使用
3. 枚舉所有 $u$ 的輕子樹並更新資料
4. 如果跑的是DFS(0)，清空所有資料
我知道聽起來很抽象，我們直接看code好了(~~其實code也蠻抽象的~~)
我們這邊偷偷用了樹壓平來枚舉子樹
```cpp=
inline void add(int col) {
cnt[col]++;
if (cnt[col] == 1) sum++;
}
void dfs(int u, int p, bool keep) {
int bson = 0;
pos[u] = ++timer;
seq[timer] = u;
for(int v : g[u]) if(v != p and sz[bson] < sz[v]) bson = v;
for(int v : g[u]) {
if(v == p or v == bson) continue;
dfs(v, u, 0); // 對輕子節點跑DFS(0)
}
if(bson) dfs(bson, u, 1); // 對重子節點跑DFS(1)
for(int v : g[u]) { // 遍歷輕子樹 更新答案
if(v == bson or v == p) continue;
for(int i = pos[v]; i < pos[v] + sz[v]; i++) {
add(col[seq[i]]);
}
}
add(col[u]);
ans[u] = sum;
if(!keep) { // 清空
sum = 0;
for(int i = pos[u]; i < pos[u] + sz[u]; i++)
cnt[col[seq[i]]]--;
}
}
```
上面這個寫法可能有點難聯想到啟發式合併，所以有另一種輕重式的證明(~~這名字是我自己取的~~)，看懂這個等下再看輕重鏈剖分應該就很容易了。
:::spoiler 證明
我們先定義輕邊和重邊，一個節點到他輕子節點的邊就是輕邊，重邊亦然。
我們知道如果 $v$ 為 $u$ 的輕子節點，那當 DFS 到 $u$ 時，$v$ 的子樹會被合併到一次。
換句話說一個點被合併的次數，就是它到根節點路徑上的輕邊數量。
接著我們知道如果 $v$ 為 $u$ 的輕子節點，那 $u$ 的子樹大小一定大於 $v$ 的子樹大小的2倍。
也就是 $sz[u] > sz[v] * 2$
所以我們每往上爬一層，子樹大小就會翻倍，最終爬到根節點時子樹大小為 $N$
因此一個點到根節點的路徑上的輕邊數量必小於等於 $log_2N$
:::
<br>
但其實這樣變得不是很好寫，所以我平常還是喜歡直接砸資料結構
如果想學更多寫法可以參考[dsu on tree](https://codeforces.com/blog/entry/44351) (~~我是不知道這和dsu有甚麼關係啦~~)
### 練習
1. [Lomsat gelral](https://codeforces.com/contest/600/problem/E)
2. [APIO 忍者調度問題](https://tioj.ck.tp.edu.tw/problems/1429)
3. [IOI Race](https://oj.uz/problem/view/IOI11_race)
---
## 樹上莫隊
這邊的樹上莫隊只是把樹用又是另一種壓平方式然後做莫隊，其實還有sqrt tree之類的東西，這邊就先不討論了(~~因為我不會~~)。
所以樹上莫隊和普通莫隊的複雜度一樣，都是 $O(N\sqrt N)$
可以處理樹上查詢**路徑資訊**的問題。
我們先看看另一種樹壓平方式，是在DFS進去和出來時加入，所以長度為$2N$。
```cpp=
void dfs(int u, int p) {
in[u] = ++timer;
seq[timer] = u;
for (int v : g[u]) {
if (v == p) continue;
dfs(v, u);
}
out[u] = ++timer;
seq[u] = u;
}
```
我們順便紀錄的進入和出去的時間，等下會用到。
但這樣要怎麼用一段連續區間表示樹上的一條路徑呢?
大家可以先自己想想看。
::: spoiler 提示 1
可以把路徑分成兩種Case
假設我們現在要求路徑 $(a, b)$
可以用是否 $a \ or \ b = LCA(a, v)$ 來討論
:::
<br>
::: spoiler 提示 2
可以用一個點在區間中的出現次數，來分辨這個點是否在路徑上。
:::
<br>
:::spoiler Tutorial
假設路徑的兩端點是 $a, b$
節點 $x$ 在樹壓平序列第一次出現的位置為 $st(x)$ 第二次出現的位置為
$ed(x)$
第一個重點是
在一個區間中，只有出現奇數次的節點會辦算入答案中。
我們可以分成兩種Case
第一種是 Case 是 $a$ 或 $b$ 為 $LCA(a, b)$
這種期況下我們可以先不失一般性的假設$a$是$LCA(a, b)$
此時的 $st(a) < st(b) < ed(b) < ed(a)$
我們可以取區間$[st(a),\ st(b)]$ 或 $[ed(b),\ ed(a)]$
這兩個都能作為代表路徑 $a$ 到 $b$ 的區間
前者會計算到路徑上點的第一次出現
後者則是會算到第二次出現
由於兩者區間沒有重疊，所以路徑上的點都只會出現 $1$ 次
第二種 Case 就是 $a$ 和 $b$ 都不等於 $LCA(a, b)$
這個情況就比較麻煩了，當然你可以把它當做$2$個 Case 1，因為你可以把它拆成 $(a, LCA(a, b))$ 和 $(b, LCA(a, b))$ 兩條路徑去做，只是稍顯麻煩，
我們可以不失一般性的假設此時的 $st(a) < ed(a) < st(b) < ed(b)$
可以保證區間 $[st(a), ed(a)]$ 和 $[st(b), ed(b)]$ 不會有交集
因為 $a$ 和 $b$ 一定不是祖先和子孫關係。
有一個實作起來稍微簡單一些的方法，就是取直接取 $[ed(a), st(b)]$，這樣就能算到 $(a, LCA(a, b))$ 的第二次出現
還有 $(b, LCA(a, b))$ 的第一次出現
但有個小問題，這樣 $LCA(a, b)$ 不會被算到，所以要記得補回去。
:::
### [例題 COT 2](https://www.spoj.com/problems/COT2/)
**題目大意**
給定一棵 $N$ 個節點的樹和 $M$ 條路徑，每個點上有一個顏色，回答每條路徑上的相異顏色個數。
:::spoiler AC code
```cpp=
#define ll loli
#include<bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define push emplace
#define sz(x) (int)(x.size())
#define re(x) reverse(all(x))
#define uni(x) x.resize(unique(all(x)) - x.begin())
#define all(x) x.begin(), x.end()
#define mem(x, v) memset(x, v, sizeof x);
#define pii pair<int, int>
#define inf 1e9
#define INF 1e18
#define mod 1000000007
#define F first
#define S second
#define IO ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
void trace_() {cerr << "\n";}
template<typename T1, typename... T2> void trace_(T1 t1, T2... t2) {cerr << ' ' << t1; trace_(t2...); }
#define trace(...) cerr << "[" << #__VA_ARGS__ << "] :", trace_(__VA_ARGS__);
const int mxN = 2e5 + 5, mxM = 2e5 + 5;
int n, m, a[mxN], dsu[mxN], lca[mxN], eu[mxM], ev[mxM], st[mxN], ed[mxN], df[mxN], dfn;
int L[mxM], R[mxM], tag[mxM], ans[mxN], vis[mxN], bsz;
vector<int> q[mxN], g[mxN];
int get(int x) {
return x == dsu[x] ? x : dsu[x] = get(dsu[x]);
}
void dfs(int u, int p = -1) {
st[u] = ++dfn;
df[dfn] = u;
for(int v : g[u]) if(v != p) dfs(v, u);
for(int i : q[u]) {
int v = u ^ eu[i] ^ ev[i];
if(vis[v]) {
lca[i] = get(v);
}
}
vis[u] = 1;
dsu[u] = p;
ed[u] = ++dfn;
df[dfn] = u;
}
int cnt[mxN], res;
inline void add(int i) {
vis[df[i]] ^= 1;
if (vis[df[i]]) {
cnt[a[df[i]]]++;
if (cnt[a[df[i]]] == 1) res++;
} else {
cnt[a[df[i]]]--;
if (cnt[a[df[i]]] == 0) res--;
}
}
signed main() {
IO;
cin >> n >> m;
bsz = sqrt(n);
vector<int> tmp;
for (int i = 1; i <= n; i++) {
cin >> a[i];
tmp.eb(a[i]);
dsu[i] = i;
}
sort(all(tmp)); uni(tmp);
for (int i = 1; i <= n; i++) {
a[i] = lower_bound(all(tmp), a[i]) - tmp.begin();
}
for (int i = 1; i < n; i++) {
int a, b; cin >> a >> b;
g[a].eb(b); g[b].eb(a);
}
for (int i = 0; i < m; i++) {
cin >> eu[i] >> ev[i];
if (eu[i] == ev[i]) {
lca[i] = eu[i];
continue;
}
q[eu[i]].eb(i);
q[ev[i]].eb(i);
}
dfs(1);
for (int i = 0; i < m; i++) {
if (st[eu[i]] > st[ev[i]]) swap(eu[i], ev[i]);
if (lca[i] == eu[i]) {
L[i] = st[eu[i]];
R[i] = st[ev[i]];
} else {
L[i] = ed[eu[i]];
R[i] = st[ev[i]];
tag[i] = lca[i];
}
}
vector<int> ord(m);
iota(all(ord), 0);
sort(all(ord), [](int x, int y){
if (L[x] / bsz != L[y] / bsz) return L[x] < L[y];
return (L[x] / bsz & 1 ? R[x] < R[y] : R[x] > R[y]);
});
memset(vis, 0, sizeof vis);
int l = L[ord[0]], r = l - 1;
for (int i : ord) {
while (r > R[i]) add(r--);
while (r < R[i]) add(++r);
while (l > L[i]) add(--l);
while (l < L[i]) add(l++);
if (tag[i]) add(st[tag[i]]);
ans[i] = res;
if (tag[i]) add(st[tag[i]]);
}
for (int i = 0; i < m; i++) {
printf("%d\n", ans[i]);
}
}
```
:::
雖然觀念不難但實作起來蠻煩躁的
### 題外話
這種樹壓平方式在檢查一兩個點是不是祖先和子孫關係時還蠻好用的，如果把一個點的第一次出現和第二次出現當作一個區間，可以發現不會有區間出現交叉的情況，只會有完全沒有交集或是一個被另一個完全包含。
## 輕重鏈剖分
輕重鏈剖分就是把樹壓平更進一步加強，原本的樹壓平只能對子樹進行操作，透過把樹切成很多條鏈，就可以暴力的在樹上做很多操作。
雖然聽起來很恐怖，但其實一點都不難，而且非常巧妙。
### 概念
我們要把樹分成很多條鏈，然後每條鏈在樹壓平之後會連續，這樣就可以用線段樹的區間操作來對鏈進行查詢或修改。
**名詞定義**
重子節點 : 子樹大小最大的子節點
輕子節點 : 不是重子節點的子節點
重邊 : 連到重子節點的邊
輕邊 : 連到輕子節點的邊
接下來的問題是要怎麼分鏈?
其實很簡單，把輕邊全部去掉，留下重邊，剩下的每個連通塊就是一條鏈。
### 性質
**對於樹上麼每條路徑，至多被拆成$O(\log N)$條鏈**
證明其實很簡單，而且就和上面樹上啟發式的第二種證明方式類似。
::: spoiler 證明
被拆稱幾條鏈其是也就是路徑上的**輕邊數量 + 1**
所以只要證明每條路徑上的輕邊數量是 $O(\log N)$ 就好
我們已經證明過一個點到根節點所經過的輕邊數量是 $O(\log N)$ (詳情請看啟發式合併證明)
然後一條路徑 $(a, b)$ 所經過的輕邊數量一定小於等於 **$a$到根所經過的輕邊數量 + $b$到根所經過的輕邊數量**
所以也是 $O(\log N)$
:::
<br>
所以如果我們想對一條路徑做區間修改，可以搭配線段樹做到$O(\log^2N)$
### 實作
也許你覺得你已經懂輕重鏈剖分在幹嘛了，但你不一定會實作。
實作方法對於沒寫過的人應該很難想出來(~~大概吧，或許是我太廢~~)
我先大概講一下我用了哪些函式和他們的作用，還有一些重要的陣列，接下來細節部分看code把它看懂就好了。
**必要的陣列**
**鏈頭陣列** : 紀錄每個點所在的鏈深度最小的那個點
**父節點陣列** : 這對之後的操作非常重要，可以用來跳鏈
**樹壓平會用到的相關陣列**
**1. 預處理DFS**
子樹大小是一定要先處理出來的，我會順便處理初每個點的重子節點，父親節點。
```cpp=
void dfs(int u, int p) {
sz[u] = 1;
fa[u] = p;
bson[u] = -1;
for (int v : g[u]) {
if(v == p) continue;
dep[v] = dep[u] + 1;
dfs(v, u);
sz[u] += sz[v];
if(bson[u] == -1 || sz[v] > sz[bson[u]]) bson[u] = v;
}
}
```
**2. 分鏈DFS**
接下來要把被重邊相連的點都連在一起，順便求出鏈頭。
```cpp=
void link(int u, int top) { // top 是當前鏈頭
tp[u] = p; // 鏈頭陣列
pos[u] = ++timer; // 紀錄每個點在序列中的出現位置
if(bson[u] != -1) link(bson[u], top);
for(int v : g[u]) {
if(v == fa[u] || v == bson[u]) continue;
link(v, v); // 開新的鏈 記得要換鏈頭
}
}
```
**3. 跳鏈**
這是最難的部分了，假如我們要對路徑$(a, b)$進行操作。
我們就會從$a, b$慢慢往上跳到他們的$LCA$
當$a, b$所在的鏈不同時就要往上跳，注意要跳到鏈頭深度較大的點，不是$a, b$深度。
```cpp=
void jump(int a, int b) {
int ans = 0;
while(tp[a] != tp[b]) {
if(dep[tp[a]] < dep[tp[b]]) swap(a, b);
// 對seq[tp[a]] ~ seq[a] 區間進行操作
a = fa[tp[a]]; // 跳到下一條鏈
}
if(dfn[a] > dfn[b]) swap(a, b);
// 不要忘記還有 seq[a] ~ seq[b]
// 最後的 a 就是 LCA
}
```
這樣就可以解決很多問題了
### [例題 Path Queries II](https://cses.fi/problemset/task/2134)
**題目大意**
給你一個樹要支援2種操作
1. 更改一個節點的值
2. 查詢路徑$a, b$上的最大值
**解法**
套個線段樹就輕鬆解決了，可以練練手感。
:::spoiler AC code
```cpp=
#include<bits/stdc++.h>
#define pb push_back
#define sz(x) (int)(x.size()
#define all(x) x.begin(), x.end()
#define int long long
#define pii pair<int, int>
#define inf 0x3f3f3f3f
#define ar(x) array<int, (x)>
#define mod 1000000007
#define io ios_base::sync_with_stdio(0); cin.tie(0)
using namespace std;
const int mxN = 2e5 + 5;
int n, q, tk, val[mxN], t[mxN], sz[mxN], fa[mxN], hson[mxN], tp[mxN], dep[mxN], dfn[mxN], seg[mxN * 4];
// hson -> heavy son
// tp -> top of chain
vector<int> g[mxN];
void dfs(int u, int p) {
sz[u] = 1;
fa[u] = p;
hson[u] = -1;
if(p != -1) dep[u] = dep[p] + 1;
for (int v : g[u]) {
if(v == p) continue;
dfs(v, u);
sz[u] += sz[v];
if(hson[u] == -1 || sz[v] > sz[hson[u]]) hson[u] = v;
}
}
void link(int u, int p) {
tp[u] = p;
dfn[u] = ++tk;
val[tk] = t[u];
if(hson[u] != -1) link(hson[u], p);
for(int v : g[u]) {
if(v == fa[u] || v == hson[u]) continue;
link(v, v);
}
}
void build(int l = 1, int r = n, int x = 1) {
if(l == r) {
seg[x] = val[l];
return;
}
int mid = l+r>>1;
build(l, mid, x<<1); build(mid+1, r, x<<1|1);
seg[x] = max(seg[x<<1], seg[x<<1|1]);
}
void modify(int pos, int v, int l = 1, int r = n, int x = 1) {
if(l == r) {
seg[x] = v;
return;
}
int mid = l+r>>1;
if(pos <= mid) modify(pos, v, l, mid, x<<1);
else modify(pos, v, mid+1, r, x<<1|1);
seg[x] = max(seg[x<<1], seg[x<<1|1]);
}
int ask(int a, int b, int l = 1, int r = n, int x = 1) {
if(a <= l and r <= b) return seg[x];
int mid = l+r>>1, res = 0;
if(a <= mid) res = ask(a, b, l, mid, x<<1);
if(b > mid) res = max(res, ask(a, b, mid+1, r, x<<1|1));
return res;
}
int query(int a, int b) {
int ans = 0;
while(tp[a] != tp[b]) {
if(dep[tp[a]] < dep[tp[b]]) swap(a, b);
ans = max(ans, ask(dfn[tp[a]], dfn[a]));
a = fa[tp[a]];
}
if(dfn[a] > dfn[b]) swap(a, b);
ans = max(ans, ask(dfn[a], dfn[b]));
return ans;
}
signed main(){
io;
cin >> n >> q;
int a, b, s;
for(int i = 1; i <= n; i++)
cin >> t[i];
for(int i = 0; i < n - 1; i++) {
cin >> a >> b;
g[a].pb(b); g[b].pb(a);
}
dfs(1, -1);
link(1, 1);
build();
while(q--) {
cin >> s >> a >> b;
if(s == 1) modify(dfn[a], b);
else cout << query(a, b) << '\n';
}
}
```
:::
## [例題 TIOJ 1171](http://www.usaco.org/index.php?page=viewproblem2&cpid=970)
**題目大意**
給定一棵樹，一開始所有節點都是白色，要支援下兩種操作。
1 . 把一個點塗成黑色
2 . 詢問點 $x$ 到所有黑色點的距離總合
這題也能用重心剖分，而且複雜度可以少一個$log$
**解法**
我們可以把點 $x$ 到所有黑點的路徑長度用表示成這樣
$\sum\limits_{v \in Black}dep_v +|Black|dep_x-2\sum\limits_{v \in Black}dep_{LCA(x, v)}$
前兩個都很好容易求出來，但最後一個好像有點不容易。
我們可以換個角度想，$dep_{LCA(x, v)}$就是 $x$到根節點 和 $v$到根節點 都會經過的邊。
所以我們可以每加入一個黑色點時就把他到根節點的路徑上標示起來
詢問的時候我們就可以查詢$x$到根節點，然後扣掉那接被重複經過的
實作上我們會習慣把邊放到較靠近葉子節點的點上，這樣就可以把邊的操作改成對點的操作了
### 練習
1. [軟件包管理器](https://uoj.ac/problem/128)
2. [Grass Planting](https://www.spoj.com/problems/GRASSPLA/)
3. [Milk Visits](http://www.usaco.org/index.php?page=viewproblem2&cpid=970)
:::spoiler 提示
其最後一題這題有$O(N)$的解法，而且好寫很多。
:::
Sign in with Wallet
Connect another wallet