【題解】ABC302 Ex - Ball Collector

題目連結

題目大意

給定一棵樹，樹上的每個節點有兩個數字 $A_i, B_i$。每經過節點時，可以從節點上的兩個數字任意拿走一個。對於 $v = 2, \dots N$，求從 $1$ 走到 $v$ 的最短路徑上，最多可以拿到幾種相異的數字？

• $2 \leq N \leq 2 \cdot 10^5$
• $1 \leq a_i, b_i \leq N$

觀察

這題是本題的簡單版本，也就是當樹是一條鏈的情況。我們建一張新的圖 $G$，把 $A_i$ 和 $B_i$ 當作節點，並對每對 $A_i, B_i$ 連接邊，題目就簡化為：對於每條邊，選擇其中一端的節點，問最多可以選到幾個節點？

如果 $G$ 有多個連通塊，因為每個連通塊之間互相獨立，我們可以分別對每個連通求出答案再加起來。因此這邊只考慮 $G$ 是一個連通塊的情況。考慮兩種情況：

1. 如果 $G$ 是一棵樹，則我們可以選到 $N - 1$ 個節點。構造的方法就是隨意選擇一個節點作為樹根，對於每條邊我們都選擇深度比較深的那個節點。這樣每個邊都不會選到重複的節點，又因為選擇的節點數量不能超過邊的數量，因此 $N - 1$ 是上限。
2. 如果 $G$ 邊的數量超過 $N$，則我們可以選到全部 $N$ 個節點。構造方法就是先對 $G$ 建立一棵生成樹，把任意一條多餘的邊的一端作為生成樹的樹根，根據 1. 生成樹上除了樹根以外的節點都可以被選到，最後再對於這條邊選擇生成樹的根節點。這樣一來 $N$ 個節點都可以被選到。

在上述的做法中，我們希望可以維護每個連通塊的節點和邊的數量。

在這題中，我們直接用走 DFS 序。每當我們進入一個新的節點 $i$ 時，要把 $A_i$ 和 $B_i$ 連邊，離開 $i$ 時要把這條邊斷開，並同時維護每個連通塊的資訊。要動態維護這些資訊我們可以用 Link Cut Tree 回滾並查集！DFS 進入一個節點的時候，先記錄並查集當前的狀態，離開前再回滾回去。

DFS 的時間複雜度為 $O(N)$，回滾並查集的合併是 $O(\log N)$，回滾為 $O(1)$，因此總時間複雜度為 $O(N \log N)$

Solution Code