BZOJ 2878 [NOI2012] 迷失游樂園：樹形 DP + 環上期望 DP 完整解析

問題大意

無向連通圖 n 點 m 邊，m = n-1 (樹) 或 m = n (單環+外向樹)。每條邊有長度。從隨機起點出發，每步等概率走向未訪問過的鄰居，直到無路可走。求經過路徑長度的期望值。起點均勻隨機，轉移概率均勻。

圖結構分類

• **樹 (m=n-1)**：無環，標準樹形 DP。
• **單環外向樹 (m=n)**：唯一一個環，環上每個節點掛一棵樹（可能退化為單點）。

核心 DP 定義

對於任意節點 x，考慮從 x 出發、不回頭走父節點方向的期望路徑長度：

• `down[x]`：向**子樹**方向走的期望長度（不含父邊）。
• `up[x]`：向**父節點**方向走的期望長度（含父邊及父節點其他分支）。

若節點度數為 d，則從 x 出發的總期望 = `(sum_{child} (w + down[child]) + up[x]) / d`（根節點無 up）。

樹形情況 (m=n-1)

1. `dfs_down(u, fa)`：後序遞歸計算 `down[u]` 和 `son[u]` (子節點數)。`down[u] = avg(w + down[v])`。
2. `dfs_up(u, fa)`：前序遞歸計算 `up[v]`。利用兄弟節點信息：`up[v] = (sum_{u的所有鄰居} (w + down) - (w_uv + down[v])) / (deg(u)-1) + w_uv`。根節點 `up[root]=0`。

單環外向樹情況 (m=n)

1. **找環**：DFS 找唯一環，存儲環上節點序列 `q[]` 和環邊權 `q2[]`。剝離環，得到若干棵以環節點為根的樹。
2. **樹部分 `down`**：對每棵樹根（環節點）執行 `dfs_down`，累加到 `down[root]`。
3. **環上 `up`**：環上節點度數 = 2(環邊) + 樹子節點數。需考慮沿環兩方向走的期望。暴力 O(k²) 計算（k=環長 ≤20），枚舉環上每個節點作為起點，沿環順/逆時針累積概率與長度。
   • 從環節點 i 出發，向順時針走：第一步進入環概率 1/(deg(i))，後續每步在環上節點 j 轉向其樹的概率為 `son[j]/(son[j]+1)`，繼續沿環概率 `1/(son[j]+1)`。累積邊權與 `down` 值。
   • 同理逆時針。`up[i]` = 兩方向期望之和。
4. **樹節點 `up`**：已知環節點 `up`，對每棵樹執行 `dfs_up` 向下傳遞。

最終答案

總期望 = `(1/n) * Σ_{i=1..n} E[i]`，其中 `E[i] = (son[i]*down[i] + up[i]) / (son[i]+1)` (非根) 或 `down[i]` (根)。環節點視為根處理。

代碼關鍵片段（節選）

// 找環 + 剝離
vector<int> q, q2; // 環節點、環邊權
bool vis[N], in_cycle;
void find_cycle(int u) {
    vis[u]=1; q.push_back(u);
    for (edge e: adj[u]) {
        int v=e.to;
        if (!vis[v]) { q2.push_back(e.w); find_cycle(v); if (in_cycle) return; }
        else if (q.size()>=2 && v != q[q.size()-2]) {
            // 找到環，截取 q 中 v 到末尾的段
            int k=0; while (q[k]!=v) ++k;
            q.erase(q.begin(), q.begin()+k);
            q2.erase(q2.begin(), q2.begin()+k);
            q2.push_back(e.w); // 閉環最後一條邊
            in_cycle=true; return;
        }
    }
    q.pop_back(); q2.pop_back();
}

// 環上 up 計算 (O(k^2))
void circle_up() {
    int sz = q.size();
    for (int i=0; i

複雜度

找環、樹 DP：O(n)。
環上 `up`：O(k²)，k≤20 → 極小。
總體 O(n)，滿足 n=100,000。


總結
NOI 2012 迷失游樂園是期望 DP 在「樹+單環」圖上的經典應用。關鍵技巧：

將期望拆解為 `down` (向下) 和 `up` (向上) 兩個方向，利用樹形 DP 遞歸計算。
環上的 `up` 利用環長極小 (≤20) 進行 O(k²) 暴力枚舉，避免複雜的環上前綴和優化。
樹掛在環上，環節點 `up` 算出後，再用標準 `dfs_up` 向下傳遞給樹內節點。

代碼中 `vector::erase(begin, begin+k)` 用於截取環片段，屬實用技巧。