樹

樹是一種特別的圖，它長的就像一顆樹。樹必須沒有環，而且要是連通的。以下就來討論樹的定義：

接下來是一些有關樹的名詞：

1. 根 (root)：有些題目會指定一個點當根，變成有根樹 (rooted tree)，根節點只有子節點沒有父節點。

2. 父節點 (parent)：對於兩個相鄰的點 $u, v$，如果 $u$ 到根節點的距離比 $v$ 到根節點的距離還要小，那麼 $u$ 就是 $v$ 的父節點。又稱親節點。

3. 子節點 (children)：如果 $u$ 是 $v$ 的父節點，那麼 $v$ 是 $u$ 的子節點。

4. 兄弟節點 (sibling)：父節點相同的節點們互為兄弟節點。

5. 子樹 (subtree)：節點 $u$ 的子樹包含 $u$、$u$ 的子節點以及他們的子樹。某個點的子樹大小就是該點形成的子樹有多少個點。

6. 森林 (forest)：一些不連通的樹構成的集合。

7. 生成樹 (spanning tree)：對於一個連通圖，我們可以從這張圖選一些邊，使得這些邊自己會形成一個包含所有點的樹，稱為此圖的生成樹。

以上圖為例， $1$ 是根節點，$2$ 是 $5$ 的父節點，$6, 7$ 是 $3$ 的子節點，$3, 4$ 互為兄弟節點，$3$ 的子樹包含 $3, 6, 7, 8$ 四個點。

尋訪一棵樹可以用 DFS 來實現，跟普通的 DFS 沒什麼兩樣。不過樹上的每個點都只有一個父節點，所以也可以用下列實作方法：

void dfs(int s, int par) {
    // process node s
    for (auto child : adj[s]) {
        if (child != par)
            dfs(child, s);
    }
}

利用變數 par 紀錄父節點的方式，在 for 迴圈內避免回頭走就行了。不須紀錄 visited 陣列。根節點沒有父節點，因此一開始呼叫這個函數的時候 par 參數要傳入非任何節點的編號（例如 $-1$）。

有時候我們需要這個節點距離樹根多遠，這時候可以慢慢往上爬到樹根，但是這樣最差可能會需要用到 $O(n)$ 時間。所以可以進行一次 DFS 預處理，之後就只要 $O(1)$ 查詢。

void dfs(int s, int par) {
    for (auto child : adj[s]) {
        if (child != par) {
            dist[child] = dist[s] + 1;
            dfs(child, s);
        }
    }
}

如果先將 dist[root] 初始化成 $0$，再對根節點 DFS 一次，dist 陣列就會儲存著每個節點到根的距離。這個每個節點到根的距離又被稱為「深度（depth）」。

尋訪樹的時候，我們可以在走完每一個小孩之後，把這個小孩的資訊傳回父親節點。

void dfs(int s, int par) {
    siz[s] = 1;
    for (auto child : adj[s]) {
        if (child != par) {
            dfs(child, s);
            siz[s] += siz[child];
        }
    }
}

這個程式可以計算出以每個點為根的子樹大小，紀錄在 size[] 陣列裡。