---
# System prepended metadata

title: 樹壓平 Euler Tour Technique
tags: [內湖高中程式競賽]

---

# 樹壓平 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