HDU 4035 Maze：樹上概率 DP 求期望通過隧道數（高斯消元 / 遞推）

問題建模

樹形迷宮 N 個房間，每房間有殺死概率 K_i%（重置回 1 號房）和出口概率 E_i%（逃脫）。從 1 號房開始，每步等概率選擇相鄰隧道。求期望通過隧道數才能逃脫。

狀態方程

設 E[u] = 從房間 u 開始期望步數。
E[u] = 1 + Σ_v∈adj(u) (1/deg(u)) × [ K_u·E[1] + (1−K_u−E_u)·E[v] ]。
邊界：出口概率視為吸收態，E[exit] = 0。

樹形 DP + 高斯消元

因為是樹，可從葉子向根遞推，將每個節點的期望表示為關於父節點期望的線性函數：
E[u] = A[u]·E[fa] + B[u]。
葉子直接建立方程，內部節點合併子節點的線性係數，最終在根節點解一元一次方程得到 E[1]，再回代求所有 E。

代碼框架

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10005;

vector g[MAXN];
double K[MAXN], E[MAXN];
double A[MAXN], B[MAXN]; // E[u] = A[u]*E[fa] + B[u]
int deg[MAXN];

void dfs(int u, int fa) {
    int m = g[u].size();
    if (m == 1 && u != 1) { // 葉子
        double p = 1 - K[u] - E[u];
        A[u] = K[u];
        B[u] = p / m; // 這裡需根據具體推導調整
        // 實際推導較繁瑣，參考斌神博客完整版
        return;
    }
    double sumA = 0, sumB = 0;
    for (int v : g[u]) if (v != fa) {
        dfs(v, u);
        sumA += A[v];
        sumB += B[v];
    }
    double p = 1 - K[u] - E[u];
    // 合併子節點貢獻建立關於 E[fa] 的線性方程
    // 具體係數推導略
}

int main() {
    // 讀入、構建樹、調用 dfs(1,0)、解根方程、輸出
    // 完整代碼較長，核心思想為樹上線性方程組消元
}

關鍵點

• 利用樹無環特性，將期望方程組轉化為線性遞推，避免 O(N³) 高斯消元。
• 若根節點方程無解（係數為 1），輸出 `impossible`。
• 精度要求 1e-4，`double` 足夠。