樹的走訪

簡介

事實上，樹的走訪也跟圖幾乎一樣，不過如果是有根樹就不需要 vis 陣列來紀錄已走過的節點，因此程式碼會好寫一點：

void dfs(int v) {
    for (auto u : g[v]) {
        dfs(v);
    }
}

不過必須注意，無根樹的話還是要向圖論一樣開 vis 陣列紀錄。

而這個章節，我們要提來介紹一些稍微進階一點的走訪技巧：

DFS 時動態維護一條路徑上的資訊

如果你想知道從根節點到達每個節點那條路徑上的某個資訊，也可以透過 DFS 來實現。以這棵樹為例：

我們想知道每個顏色圈起來的部分（也就是根節點到每個節點路徑上）的每個點權（黃色數字）出現次數，就可以使用 DFS 來實現：

void dfs(int v) {
    w[v]++; // 更新點權出現次數
    ans[v] = w[v]; // 更新答案
    for (auto u : g[v]) {
        dfs(u, path);
    }
    w[v]--; // rollback (回滾)
}

可以注意到，我們每次進入節點時，都會更新 w[v]，並在離開節點時將 w[v] 減回去（這個動作稱為 rollback），這樣就可以維護一條路徑上每個點權出現次數。當然，這個技巧還可以搭配其他資料結構來維護更複雜的資訊（比如中位數等等）。