# 樹壓平 Euler Tour Technique
在[前面的章節](https://hackmd.io/@ShanC/Lowest-Common-Ancestor#%E8%A4%87%E7%BF%92%E6%99%82%E9%96%93%E6%88%B3%E8%A8%98)講過時間戳記，這邊就把它單獨拿來玩玩。要記得，時間戳記是 DFS 原有的性質，因此很多地方都用的到它
## 複習時間戳記
時間戳記是 DFS 本身就會有的特性之一，你應該要知道才對，因為在最基礎的[這篇](https://hackmd.io/@ShanC/bfs_dfs#%E6%99%82%E9%96%93%E6%88%B3%E8%A8%98)講過了
### 程式碼實作
我們可以在上述遞迴版本的程式碼中加入:
- $d[i]$: 發現節點 $i$ 的時間 (discovery time)
- $f[i]$ : 節點 $i$ 完成所有鄰居拜訪的時間 (finishing time)
```cpp
void dfs_time(int u, int pre) {
d[u] = ++timestamp; // 紀錄發現時間
for (int &v : g[u]) {
if (v != pre) dfs_time(v, u);
}
f[u] = ++timestamp; // 紀錄結束時間
}
```
以下圖為例，我們可以把時間戳記當作是一個計時器
<center>
<img src="https://hackmd.io/_uploads/ByPVHVv_xg.png" style="margin: 0 auto; display: block; width: 600px">
</center>
### 括號定理
把所有節點 $v$ 的發現與結束時間畫在數線上，會形成好幾個區間
<center>
<img src="https://hackmd.io/_uploads/Bkq8VG__gx.png" style="margin: 0 auto; display: block; width: 600px">
</center>
藉由上圖會發現，對於任兩節點 $u$ 與 $v$ 在樹中 :
1. 如果區間 $[d[u], f[u]]$ 包含 $[d[v], f[v]]$，則 $u$ 為 $v$ 的祖先
2. 如果區間 $[d[v], f[v]]$ 包含 $[d[u], f[u]]$，則 $u$ 為 $v$ 的後代
3. 如果區間 $[d[u], f[u]]$ 與 $[d[v], f[v]]$ 沒有交集，則 $u$ 與 $v$ 沒有血緣關係
可以得到推論 : 在一棵樹中，$d[u]<d[v]<f[v]<f[u]$ 若且唯若，$v$ 是 $u$ 的後代
## 樹壓平 Euler Tour Technique
從上圖可以觀察出來，其實用 DFS 走訪樹，就相當於在圖上走歐拉迴路 (邊不重複的迴路)，Euler Tour Technique 因此得名。中文圈大家都說「樹壓平」也挺有意思，因為它真的是把樹壓平成直線的手段。樹壓平最常用來做 RMQ (區間詢問)，因此最麻煩的是結合其他區間查詢的資料結構一起玩。因為我蠻討厭維護資料結構的，所以這篇不討論那堆討人厭的東西
### 直接 DFS 的問題
設樹上每個節點都有權重，很多題目都很愛 :
- 給 $q$ 次詢問
- 每次詢問中會有兩種操作 :
- 修改權種值
- 詢問某棵子樹的權重和 (or 最大/最小)
這種題目每次修改值都會影響到整棵子樹。在之前的章節其實有說過，直接 DFS 樹上前綴和、後綴和與差分可以解決這個問題，只是他們比較偏離線的作法，$O(n)$ 跑起來會很慢。如果要做線上即時處理，以競程的習慣來說應該要有個 $O(\log n)$ 的複雜度
### 原理說明
注意到，樹壓平後的每個**區間**都代表一棵**子樹**。因此
$$
\text{對子樹修改值}=\text{對區間修改值}
$$
既然可以修改區間，那就可以引入 Fenwick tree、segment tree 與根號算法來求解區間問題
## 例題說明 : [Subtree Queries](https://cses.fi/problemset/task/1137)
### 題目
給一棵有編號的樹 ($1$~$n$)，$1$ 為根，每個節點都有權重。給 $q$ 比詢問，共有兩種問題 :
1. 修改節點 $s$ 的值變成 $x$
2. 求出 $s$ 為根的子樹權重和
### 限制
- $1 \le n, q \le 2 \cdot 10^5$
- $1 \le a,b, s \le n$
- $1 \le v_i, x \le 10^9$
### 題解
原理跟[剛才](#原理說明)說的一樣，首先一樣是先建立時間戳記的陣列 `d[]` 與 `f[]`
<center>
<img src="https://hackmd.io/_uploads/ryCerG1tel.png" style="margin: 0 auto; display: block; width: 600px">
</center>
接下來我們會得到一個區間，若給每個節點權重，我們可以在抵達該點的時間加上值，舉例如下圖 : 給定節點的權重分別為 $4,2,5,2,1$
<center>
<img src="https://hackmd.io/_uploads/SyavHf1txg.png" style="margin: 0 auto; display: block; width: 600px">
</center>
假設我們要查詢 $3$ 這個子樹的總和，相當於求區間 $[4, 9]$ 的總和，也就是 $5+2+1=8$
不難發現，由於離開的格子都用不到，因此可以省去離開的時間戳記
```cpp
void dfs_time(int u, int pre) {
d[u] = ++timestamp; // 紀錄發現時間
for (int &v : g[u]) {
if (v != pre) dfs_time(v, u);
}
f[u] = timestamp; // 紀錄結束時間
}
```
實際上就會長這樣
<center>
<img src="https://hackmd.io/_uploads/rk97OMktll.png" style="margin: 0 auto; display: block; width: 600px">
</center>
### 實作程式碼
`val[]` 是每個節點的權重、`MXN` 是最大節點數，其餘變數名稱都跟上面長的一樣。至於 Fenwick tree 的部分，請用你自己的模板
```cpp
/* 略 */
void dfs_time(int u, int pre) {
d[u] = ++timestamp; // 紀錄發現時間
for (int &v : g[u]) {
if (v != pre) dfs_time(v, u);
}
f[u] = timestamp; // 紀錄結束時間
}
int main() {
/* 輸入的部分略 */
dfs_time(1, 0);
BIT bit(MXN); // 這邊使用 Fenwick tree 來維護前綴和
for (int i = 1; i <= n; i++)
bit.update(d[i], val[i]);
while (q--) {
int mod, s, x;
cin >> mod;
if (mod == 1) {
cin >> s >> x;
bit.update(d[s], x - val[s]);
val[s] = x;
}
else {
cin >> s;
cout << bit.query(d[s], f[s]) << '\n';
}
}
return 0;
}
```
## 可能會採的雷
要注意樹壓平只跟「子樹」有關，如果權重的維護是在整條路徑上，那可能需要其他方法像是 (輕重) 樹鏈剖分
## 題目練習
[CSES Subtree Queries](https://cses.fi/problemset/task/1137)
[CSES Path Queries](https://cses.fi/problemset/task/1138)
[Codeforces 383C. Propagating tree](https://codeforces.com/problemset/problem/383/C)
[Codeforces 877E. Danil and a Part-time Job](https://codeforces.com/problemset/problem/877/E)
[AtCoder Beginner Contest 294G - Distance Queries on a Tree](https://atcoder.jp/contests/abc294/tasks/abc294_g)
----
## 參考資料
[海大競程 - Tree Algorithm 2](https://hackmd.io/@LeeShoWhaodian/2025I2CP_tree2#/)
----
> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2025/8/24
Sign in with Wallet
Connect another wallet