Codeforces 🟢 CF2053E. Resourceful Caterpillar Sequence

題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 CF2053E Resourceful Caterpillar Sequence

Problem Statement

題目簡述

給定一棵 $n$ 個節點的樹。定義一個「毛毛蟲」由 $(p, q)$ 表示，佔據從 $p$ 到 $q$ 的簡單路徑上的所有節點。

Nora 和 Aron 輪流移動毛毛蟲，Nora 先手。

• Nora 的回合：選擇一個與 $p$ 相鄰但不被毛毛蟲佔據的節點 $u$，將整個毛毛蟲向 $u$ 方向移動一步。
• Aron 的回合：選擇一個與 $q$ 相鄰但不被毛毛蟲佔據的節點 $v$，將整個毛毛蟲向 $v$ 方向移動一步。

當 $p$ 變成葉子時 Nora 獲勝；當 $q$ 變成葉子時 Aron 獲勝。若初始時 $p, q$ 同時為葉子，或遊戲超過 $10^{100}$ 輪未結束，則平局。

求有多少個有序對 $(p, q)$（$p \neq q$）使得 Aron 獲勝。

Constraints

約束條件

• $2 \le n \le 2 \times 10^5$

---

思路：換根 DP

後手必勝局面分析

關鍵觀察：勝負在兩輪內決定

假設某玩家在第 $k$ 輪沒有必勝策略，但在第 $k+2$ 輪有必勝策略。這是不可能的，因為對手總是可以 撤銷 上一輪的移動，使狀態回到第 $k$ 輪之前。

因此：如果有人獲勝，必定在前 2 輪內決定。

為了方便後續討論，我們先計算每個節點 $u$ 到最近葉子節點的距離，記為 $\text{dist}[u]$（葉子本身的距離為 0）。
根據 $\text{dist}[u]$ 的值，將所有節點分為三類：

節點分類 $(L, N, C)$

1. 葉子集合 $L$ (Leaf)：$\text{dist}[u] = 0$。即樹上的葉子。
2. 葉子鄰居集合 $N$ (Neighbor)：$\text{dist}[u] = 1$。即與葉子直接相鄰的非葉子節點。
3. 中心集合 $C$ (Center)：$\text{dist}[u] \ge 2$。即距離任何葉子都至少 2 步的節點。

圖示範例

graph TD
    subgraph "節點分類"
        C3_1(("C<br>dist=3")):::center
        C2_1(("C<br>dist=2")):::center
        C2_2(("C<br>dist=2")):::center
        N1(("N<br>dist=1")):::neighbor
        N2(("N<br>dist=1")):::neighbor
        N3(("N<br>dist=1")):::neighbor
        N4(("N<br>dist=1")):::neighbor
        L1(("L<br>dist=0")):::leaf
        L2(("L<br>dist=0")):::leaf
        L3(("L<br>dist=0")):::leaf
        L4(("L<br>dist=0")):::leaf
        L5(("L<br>dist=0")):::leaf
        
        C3_1 --- C2_1
        C3_1 --- C2_2
        C2_1 --- N1
        C2_1 --- N2
        C2_2 --- N3
        C2_2 --- N4
        N1 --- L1
        N2 --- L2
        N3 --- L3
        N3 --- L4
        N4 --- L5
    end
    
    classDef leaf fill:#90EE90,stroke:#228B22,color:#000
    classDef neighbor fill:#FFD700,stroke:#DAA520,color:#000
    classDef center fill:#87CEEB,stroke:#4682B4,color:#000

• 🟢 綠色 (L)：葉子節點，$\text{dist} = 0$
• 🟡 黃色 (N)：葉子的鄰居，$\text{dist} = 1$
• 🔵 藍色 ©：中心節點，$\text{dist} \ge 2$

獲勝條件分析

根據「勝負在兩輪內決定」的觀察，Aron 要獲勝，必須滿足以下兩個條件之一：

Case 1：初始必勝（第 0 輪）

條件：$p \notin L$ 且 $q \in L$

• 遊戲開始時，$q$ 已經是葉子，Aron 直接獲勝。
• 注意：若 $p$ 也是葉子（即 $p, q$ 都是葉子），則根據規則是平局，不算 Aron 獲勝。
• 計數：$q$ 從 $|L|$ 個葉子中選，$p$ 從 $n - |L|$ 個非葉子中選，共 $|L| \times (n - |L|)$ 對。

Case 2：過程必勝（第 2 輪）

當初始狀態 $p, q$ 都不是葉子時，需要進一步分析：

前提：Nora 首輪不能獲勝

• Nora 想在第 1 輪獲勝，她需要將 $p$ 移動到某個葉子 $\ell$。
• 這要求 $p$ 有一個相鄰的葉子，即 $\text{dist}[p] = 1$（$p \in N$）。
• 因此，若 $p \in C$（$\text{dist}[p] \ge 2$），Nora 第 1 輪無法獲勝。

條件：$p \in C$ 、 $q \notin L$，且 $q$ 往 $p$ 方向的鄰居 $x \in N$

詳細推導：

1. 遊戲開始時，$p, q$ 都不是葉子，無人獲勝。
2. Nora 的第 1 輪：Nora 必須移動頭部 $p$。由於 $p \in C$，$p$ 的所有鄰居都不是葉子，Nora 無法立即獲勝。無論 Nora 怎麼移動，毛毛蟲整體會「滑動」一步：
   • 新的頭部變成 $p$ 的某個鄰居 $u$。
   • 尾部 $q$ 會收縮到路徑上的下一個節點 $x$（即原本 $q$ 往 $p$ 方向的鄰居）。
3. Aron 的第 2 輪：此時尾部在 $x$。若 $x \in N$（$\text{dist}[x] = 1$），則 $x$ 有一個相鄰的葉子 $\ell$。Aron 可以將尾部移動到 $\ell$，獲勝！
4. 關鍵洞察：Nora 無法阻止尾部收縮到 $x$。無論她選擇往哪個方向移動頭部，尾部的收縮方向是固定的（沿著 $q \to p$ 的路徑）。

為何 $x$ 必須在 $N$ 中？

• 若 $x \in L$（$x$ 是葉子）：這不可能發生。因為 $x$ 位於 $q \to p$ 路徑上，$x$ 至少有兩個鄰居（$q$ 側和 $p$ 側），故 $x$ 的度數 $\ge 2$，不是葉子。唯一的例外是毛毛蟲長度為 2（即 $x = p$），但若 $p$ 是葉子則 Nora 在第 0 輪就獲勝，這已包含在 Case 1 中且與 $p \in C$ 矛盾。
• 若 $x \in C$（$\text{dist}[x] \ge 2$）：$x$ 旁邊沒有葉子，Aron 無法在第 2 輪獲勝。根據「勝負在兩輪內決定」，此時遊戲將平局。
• 所以 $x \in N$ 是 Aron 在第 2 輪獲勝的必要條件。

毛毛蟲移動示意圖

• 粗黑框：毛毛蟲佔據的節點
• ★：頭部、●：尾部
• 顏色表示節點類型：🟢L / 🟡N / 🔵C / ⬜其他

初始狀態

頭 $p \in C$，尾 $q \notin L$，路徑上有 $x \in N$

graph LR
    subgraph "初始狀態"
        direction LR
        Other1(("  ·  ")):::other
        U1(("  u  ")):::center
        P1((" p★ ")):::caterpillar_C
        M1(("  ·  ")):::caterpillar_other
        M2(("  ·  ")):::caterpillar_other
        X1(("  x  ")):::caterpillar_N
        Q1((" q● ")):::caterpillar_N
        More1(("  ·  ")):::other
        L1(("  ℓ  ")):::leaf
        
        Other1 ~~~ U1
        U1 --- P1
        P1 --- M1
        M1 --- M2
        M2 --- X1
        X1 --- Q1
        Q1 ~~~ More1
        X1 --- L1
    end
    
    classDef leaf fill:#90EE90,stroke:#228B22,color:#000
    classDef neighbor fill:#FFD700,stroke:#DAA520,color:#000
    classDef center fill:#87CEEB,stroke:#4682B4,color:#000
    classDef other fill:#D3D3D3,stroke:#808080,color:#666
    classDef caterpillar_C fill:#87CEEB,stroke:#000,stroke-width:4px,color:#000
    classDef caterpillar_N fill:#FFD700,stroke:#000,stroke-width:4px,color:#000
    classDef caterpillar_other fill:#D3D3D3,stroke:#000,stroke-width:4px,color:#000

• 毛毛蟲佔據：$p \to \cdot \to \cdot \to x \to q$（5 個節點，粗黑框）

Nora 移動後

頭移動到 $u$，尾收縮到 $x$

graph LR
    subgraph "Nora 移動後"
        direction LR
        Other2(("  ·  ")):::other
        U2((" u★ ")):::caterpillar_C
        P2(("  p  ")):::caterpillar_C
        M3(("  ·  ")):::caterpillar_other
        M4(("  ·  ")):::caterpillar_other
        X2((" x● ")):::caterpillar_N
        Q2(("  q  ")):::neighbor
        More2(("  ·  ")):::other
        L2(("  ℓ  ")):::leaf
        
        Other2 ~~~ U2
        U2 --- P2
        P2 --- M3
        M3 --- M4
        M4 --- X2
        X2 ~~~ Q2
        Q2 ~~~ More2
        X2 --- L2
    end
    
    classDef leaf fill:#90EE90,stroke:#228B22,color:#000
    classDef neighbor fill:#FFD700,stroke:#DAA520,color:#000
    classDef center fill:#87CEEB,stroke:#4682B4,color:#000
    classDef other fill:#D3D3D3,stroke:#808080,color:#666
    classDef caterpillar_C fill:#87CEEB,stroke:#000,stroke-width:4px,color:#000
    classDef caterpillar_N fill:#FFD700,stroke:#000,stroke-width:4px,color:#000
    classDef caterpillar_other fill:#D3D3D3,stroke:#000,stroke-width:4px,color:#000

• 毛毛蟲佔據：$u \to p \to \cdot \to \cdot \to x$（粗黑框）
• 尾部 $x \in N$，旁邊有葉子 $\ell$

Aron 移動後（獲勝！）

graph LR
    subgraph "Aron 獲勝"
        direction LR
        Other3(("  ·  ")):::other
        U3(("  u  ")):::center
        P3((" p★ ")):::caterpillar_C
        M5(("  ·  ")):::caterpillar_other
        M6(("  ·  ")):::caterpillar_other
        X3(("  x  ")):::caterpillar_N
        L3((" ℓ● ")):::caterpillar_L
        
        Other3 ~~~ U3
        U3 --- P3
        P3 --- M5
        M5 --- M6
        M6 --- X3
        X3 --- L3
    end
    
    classDef leaf fill:#90EE90,stroke:#228B22,color:#000
    classDef center fill:#87CEEB,stroke:#4682B4,color:#000
    classDef neighbor fill:#FFD700,stroke:#DAA520,color:#000
    classDef other fill:#D3D3D3,stroke:#808080,color:#666
    classDef caterpillar_C fill:#87CEEB,stroke:#000,stroke-width:4px,color:#000
    classDef caterpillar_N fill:#FFD700,stroke:#000,stroke-width:4px,color:#000
    classDef caterpillar_L fill:#90EE90,stroke:#000,stroke-width:4px,color:#000
    classDef caterpillar_other fill:#D3D3D3,stroke:#000,stroke-width:4px,color:#000

• 尾部 $\ell$ 是葉子（$L$ 類）→ Aron 獲勝！

換根 DP 計數

我們需要統計 Case 2 的數量。回顧條件：

• $p \in C$（$\text{dist}[p] \ge 2$）
• $q \notin L$（$\text{dist}[q] \ge 1$）
• $q$ 往 $p$ 方向的第一個鄰居 $x \in N$（$\text{dist}[x] = 1$）

問題轉化

對於每個 $q$（非葉子），我們要計算有多少個 $p \in C$ 滿足：從 $q$ 往 $p$ 方向走的第一個鄰居 $x$ 恰好屬於 $N$。

換句話說，對於 $q$ 的每個鄰居 $x$：

• 若 $x \in N$，則「從 $q$ 經過 $x$ 能到達的所有節點」中的 $C$ 類節點都是合法的 $p$。
• 這等價於以 $q$ 為根時，$x$ 子樹內的 $C$ 類節點。

這是一個典型的「對每個節點，統計各方向子樹內某類節點數量」的問題，適合用 換根 DP 解決。

狀態定義

以任意節點（如節點 0）為根建樹後：

狀態	定義
sz[u]	以 $u$ 為根的子樹中，$C$ 類節點的數量（即 $\text{dist}[v] \ge 2$ 的節點數）。
f[u]	當 $q = u$ 時，滿足 Case 2 條件的合法 $p$ 的總數。
cnt[2]	整棵樹中 $C$ 類節點的總數（預處理得到）。

整體流程

Step 1：BFS 預處理距離

從所有葉子開始做多源 BFS，計算每個節點到最近葉子的距離 dist[u]。同時統計 cnt[0]、cnt[1]、cnt[2] 分別為 $L$、$N$、$C$ 類節點的數量。

Step 2：第一次 DFS（Bottom-up）

目標：計算 sz[u] 和來自子節點方向的貢獻

對於節點 $u$，遍歷其所有子節點 $v$：

1. 累加子樹大小：sz[u] += sz[v]
2. 計算貢獻：若 $v \in N$（dist[v] == 1），則 $v$ 是 $u$ 往子樹方向的鄰居。此時 $v$ 子樹內的所有 $C$ 類節點都是合法的 $p$（因為從 $q=u$ 往這些 $p$ 走，第一步就是走到 $v \in N$）。故 f[u] += sz[v]。

Step 3：第二次 DFS（Top-down / Reroot）

目標：計算來自父節點方向的貢獻

當我們從 $u$ 走到子節點 $v$ 時，從 $v$ 的視角來看，$u$ 變成了 $v$ 的一個鄰居（往「父節點方向」）。

若 $u \in N$（dist[u] == 1），則 $u$ 方向的所有 $C$ 類節點都是 $v$ 的合法 $p$。

$u$ 方向的 $C$ 類節點數量 = 整棵樹的 $C$ 類總數 - $v$ 子樹內的 $C$ 類數量 = cnt[2] - sz[v]

故 f[v] += (cnt[2] - sz[v])。

Step 4：計算最終答案

答案公式

$$\text{ans} = \underbrace{|L| \times (n - |L|)}_{\text{Case 1}} + \underbrace{\sum_{u: \text{dist}[u] \ge 1} f[u]}_{\text{Case 2}}$$

• Case 1：$q \in L$，$p \notin L$，共 cnt[0] * (n - cnt[0]) 對。
• Case 2：對所有非葉子節點 $u$（$\text{dist}[u] \ge 1$），累加 f[u]。

複雜度分析

• 時間複雜度：$\mathcal{O}(n)$。標記距離、兩次 DFS 遍歷均為線性時間。
• 空間複雜度：$\mathcal{O}(n)$。用於儲存圖、距離陣列與 DP 狀態。

---

Code

from collections import deque

def solve():
    n = int(input())

    g = [[] for _ in range(n)]
    deg = [0] * n
    for _ in range(n - 1):
        u, v = map(lambda x: int(x) - 1, input().split())
        g[u].append(v)
        g[v].append(u)
        deg[u] += 1
        deg[v] += 1

    q = deque([u for u in range(n) if deg[u] == 1])
    dist = [0 if deg[u] == 1 else float('inf') for u in range(n)]
    while q:
        u = q.popleft()
        for v in g[u]:
            if dist[v] == float('inf'):
                dist[v] = dist[u] + 1
                q.append(v)

    cnt = [0] * 3
    for u in range(n):
        cnt[min(dist[u], 2)] += 1

    sz = [0] * n
    f = [0] * n

    def dfs(u, fa):
        # sz[u] = 1 if dist[u] > 1 else 0
        # for v in g[u]:
        #     if v == fa:
        #         continue
        #     dfs(v, u)
        #     sz[u] += sz[v]
        #     if dist[v] == 1:
        #         f[u] += sz[v]
        st = [(u, fa, 0)]
        while st:
            u, fa, i = st.pop()
            if i == 0:
                sz[u] = 1 if dist[u] > 1 else 0
            if i > 0:
                v = g[u][i - 1]
                sz[u] += sz[v]
                if dist[v] == 1:
                    f[u] += sz[v]
            for j in range(i, len(g[u])):
                v = g[u][j]
                if v == fa:
                    continue
                st.append((u, fa, j + 1))
                st.append((v, u, 0))
                break

    def reroot(u, fa):
        # for v in g[u]:
        #     if v == fa:
        #         continue
        #     if dist[u] == 1:
        #         f[v] += (cnt[2] - sz[v])
        #     reroot(v, u)
        st = [(u, fa, 0)]
        while st:
            u, fa, i = st.pop()
            for j in range(i, len(g[u])):
                v = g[u][j]
                if v == fa:
                    continue
                if dist[u] == 1:
                    f[v] += (cnt[2] - sz[v])
                st.append((u, fa, j + 1))
                st.append((v, u, 0))
                break

    dfs(0, -1)
    reroot(0, -1)

    ans = cnt[0] * (n - cnt[0])
    for u in range(n):
        if dist[u] >= 1:
            ans += f[u]

    print(ans)

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()

寫在最後

PROMPT

這裡什麼都沒有。

對於將 Recursion DFS 轉換為 Iteration DFS 已經越來越熟練了。

靈機一動想要在筆記加上圖示範例，結果陷入了大坑之中。即使用了 AI 輔助還是一直給我錯誤的結構圖，還是得自己手動調整。