樹的應用

樹有各式各樣的應用問題，雖然沒有辦法全部都介紹，但是我們可以透過以下幾個最經典的例子討論如何在樹上思考！

回顧一下樹的性質，樹上任一個頂點對（兩相異頂點）都只存在唯一路徑。而有時候我們在乎擁有最大距離的路徑，這條路徑就被稱為直徑（diameter）。

讀者可以發現，直徑有可能有很多條，畢竟可以有好幾條長度最長的簡單路徑。那要怎麼找到任何一條直徑呢？這裡需要一個性質：

證明

為什麼呢？我們使用反證法，想像我們把樹上的某一組最遠的點對 $(u, v)$ 拉到兩端，並假設我們想幫點 $x$ 找到距離他最遠的點。

為了方便起見，我們把 $a$ 到 $b$ 的路徑寫做 $\mathrm{Path}(a, b)$。

假設點 $x$ 到直徑上的最近點是 $p$，並不失一般性假設 $p$ 到 $u$ 比到 $v$ 遠，如上圖。那麼，如果 $x$ 真正的最遠點是不能做為直徑端點的 $y$，那麼我們會有

• $\mathrm{Path}(y, p)$，會比 $\mathrm{Path}(p, u)$ 還要短。

不然 $\mathrm{Path}(y, u)$ 或 $\mathrm{Path}(y, v)$ 就能因此不比 $\mathrm{Path}(u, v)$ 還要短，造成 $y$ 可以是直徑端點。

既然如此，那麼路徑 $\mathrm{Path}(y, p) + \mathrm{Path}(p, x)$，就肯定會比 $\mathrm{Path}(u, p) + \mathrm{Path}(p, x)$ 還要短，這表示 $\mathrm{Path}(x, y)$ 比 $\mathrm{Path}(x, u)$ 還要短，矛盾！

因此，我們先找一個點當根，做一次 DFS 找到距離他最遠的點。然後從這個最遠點再做一次 DFS，再找到距離最遠點最遠的點，連接這兩個點的路徑就是直徑。

int diameter() {
    int root = 1;
    dfs(root, -1);
    int point1 = max_element(dist.begin() + 1, dist.end()) - dist.begin();
    dfs(point1, -1);
    int point2 = max_element(dist.begin() + 1, dist.end()) - dist.begin();
    // point1, point2 是直徑兩端點
    return dist[point2];
}

這裡省略了 DFS 的部分以及 dist 陣列，這兩個部分請回去參考樹。

當然，有「直徑」就有「圓心」。

讀者可以發現，當直徑長度為奇數時，圓心會落在樹的邊上，這並沒有影響我們的定義，因為圓心確實沒有被定義成樹上的任意一個節點。不過倒是有一個問題：直徑不是可能有很多條嗎？這樣圓心會不會有好幾個？

實際上，有以下性質存在：

證明

我們使用反證法。考慮任意兩條直徑，如果他們的圓心不相同，則我們可以找到這兩個圓心所形成的路徑，畢竟這條路徑以兩個圓心為端點，所以他不可能同時和任何一條直徑上、圓心兩側的邊相交。這表示我們可以找到一條比直徑更長的路徑，他的長度是兩條「一半的直徑」加上這兩個圓心路徑的長度，造成矛盾。

因此，圓心其實只有一個！

以上的定義全部都可以推廣到帶正邊權的樹，可以想像成是一條長度 $w$ 的邊上有額外 $w-1$ 個點在上面就行。

重心是樹上很重要的點，我們先來看看他的定義。

int find_centroid(int u, int par, const int n) {
    int res = -1;
    sz[u] = 1, mxsz[u] = 0;
    for (auto child : adj[u]) {
        if (child != par) {
            find_centroid(child, par, n);
            sz[u] += sz[child];
            mxsz[u] = max(mxsz[u], sz[child]);
            if (res == -1 || mxsz[res] > mxsz[child])
                res = child;
        }
    }
    // 移除 u 時，在 u 頭上的那個連通塊大小，恰好能由 n - sz[u] 算出來
    mxsz[u] = max(mxsz[u], n - sz[u]);
    if (res == -1 || mxsz[res] > mxsz[u])
        res = u;
    return res;
}

這裡用到的做法是邊在計算子樹大小 sz[] 陣列的同時，邊順便找到「移除」一個點時，最大的連通塊大小是究竟有多大，並存在 mxsz[] 陣列內。只要比較 mxsz[] 的大小，最小的那個就是重心了。

重心有許多酷炫的性質，例如：

這個作法也給了我們找重心的另一種方法：首先隨意選一個根節點 DFS，找出所有點的子樹大小。然後從根開始往下，沿著「子樹大小 $> \frac{N}{2}$」的點走，直到不能走時就會抵達重心。

int find_centroid(int u, int par, const int n) {
    for (auto child : adj[u]) {
        if (child != par && 2 * sz[child] > n)
            return find_centroid(child, u, n);
    }
    return u;
}

這份程式碼的缺點就是 sz[] 陣列得預先算好，所以得跑兩次 DFS，常數比前面那份程式碼略大了一些，但相當簡潔。

不過，讀者可能會好奇：重心是否和圓心一樣，一棵樹上只會有一個呢？

答案是否定的，實際上：

這部份的證明不太困難，讀者可以用前面講過的一些性質來做思考，相信能夠自行體會。

樹上問題最大的特色就是我們可以很容易用遞迴的方式去思考解題方式。我們可以把每個子樹想成是自己的一個小問題，對於以點 $u$ 為根的子樹來說，他的答案往往可以被分解成「以他的小孩 $v_1, v_2, \dots, v_c$ 為根的各個子樹的答案」與 $u$ 自己合併的結果。舉例來說，在計算子樹大小時，$u$ 的子樹大小就是 $v_1, v_2, \dots, v_c$ 的子樹大小總和再加上 $1$。解決許多樹上問題的關鍵，就是嘗試找到子樹和他們的父節點如何合併算出答案。

以這題來說，不妨直接定義每個子問題為「該子樹下的最大匹配」。對於一個子樹 $v$ 來說，如果 $v$ 不是匹配的端點，那麼他就可以連上他的父節點，並且把這條邊加進匹配。我們要計算子樹 $u$ 下的最大匹配時，先分別求出 $u$ 的所有小孩 $v_1, v_2, \dots, v_c$ 子樹的最大匹配，然後再一一檢查 $v_1, v_2, \dots, v_c$ 是否是匹配的端點。如果有一個點 $v_i$ 不是端點的話，就把 $v_i$ 和 $u$ 配對。