2673. 「NOI2012」迷失游乐园 题解

题目分析

我们有一个 $n$ 个点 $m$ 条边的无向连通图，且 $m = n$ 或 $m = n-1$，即要么是树，要么是基环树（只有一个环）。

从任意一个点出发（每个点作为起点的概率相等），每次随机走向一个未访问过的相邻点，直到无路可走（所有相邻点都访问过）。求这条路径的期望长度。

---

基础概念

1. 状态定义

• $deg[u]$：点 $u$ 的度数（邻居数）
• $son[u]$：$u$ 的子节点集合（在树形结构中）
• $fa[u]$：$u$ 的父节点（在树形结构中）

2. 重要结论

从某个点 $u$ 出发，第一步有 $deg[u]$ 种可能方向：

• 如果 $u$ 不是起点，那么从父节点方向来的点已经访问过，只能走向子节点
• 如果 $u$ 是起点，可以走向任意邻居

---

第一部分：树的情况（$m = n-1$）

1. 第一次 DP：计算向下走的期望

定义 $down[u]$：从 $u$ 出发，只往子树方向走（不回头走向父节点）的期望路径长度。

对于叶子节点：$down[u] = 0$

对于非叶子节点： 设 $u$ 有 $k$ 个子节点 $v_1, v_2, ..., v_k$，边权分别为 $w_1, w_2, ..., w_k$ 则：

$$down[u] = \frac{\sum_{i=1}^k (down[v_i] + w_i)}{k} $$

解释：从 $u$ 出发，以 $\frac{1}{k}$ 的概率走向每个子节点 $v_i$，然后从 $v_i$ 继续向下走的期望是 $down[v_i] + w_i$。

void dfs_down(int u, int fa) {
    int cnt = 0;
    double sum = 0.0;
    for (auto &edge : g[u]) {
        int v = edge.to;
        double w = edge.w;
        if (v == fa) continue;
        dfs_down(v, u);
        cnt++;
        sum += down[v] + w;
    }
    if (cnt > 0) {
        down[u] = sum / cnt;
    } else {
        down[u] = 0.0;
    }
}

2. 第二次 DP：计算向上走的期望（换根 DP）

定义 $up[u]$：从 $u$ 出发，第一步走向父节点，然后继续随机游走的期望路径长度。

对于根节点（任意选一个根）：$up[root] = 0$

对于非根节点 $u$，父节点为 $f$： 设 $f$ 有邻居：$u$（子节点）和其他子节点 $v_1, v_2, ..., v_k$

从 $u$ 出发走向 $f$ 后，在 $f$ 处有几种选择：

1. 走向 $f$ 的父节点（如果 $f$ 不是根）
2. 走向 $f$ 的其他子节点

设 $f$ 的度数为 $deg[f]$，则：

• 如果 $f$ 是根节点：从 $f$ 有 $deg[f]$ 个方向可选
• 如果 $f$ 不是根节点：从 $f$ 有 $deg[f]-1$ 个方向可选（因为从 $u$ 来的方向已经访问过）

情况 1：$f$ 是根节点

$$up[u] = w_{u,f} + \frac{\sum_{v \in son(f), v \neq u} (down[v] + w_{f,v}) + up[f]}{deg[f]-1} $$

注意：$up[f]$ 是 $f$ 向上走的期望，但 $f$ 是根，所以 $up[f]=0$

情况 2：$f$ 不是根节点

$$up[u] = w_{u,f} + \frac{\sum_{v \in son(f), v \neq u} (down[v] + w_{f,v}) + up[f]}{deg[f]-1} $$

但是 $up[f]$ 需要特殊处理，因为 $f$ 向上走可能走到 $u$ 的祖先。

更通用的公式： 设 $E_f$ 表示从 $f$ 出发（不包含从 $u$ 来的方向）的期望：

$$E_f = \frac{\sum_{v \in neighbor(f), v \neq u} (从 v 方向走的期望)}{deg[f]-1} $$

其中：

• 如果 $v$ 是 $f$ 的子节点：期望 = $down[v] + w_{f,v}$
• 如果 $v$ 是 $f$ 的父节点：期望 = $up[f] + w_{f,fa[f]}$

因此：

$$up[u] = w_{u,f} + E_f$$

void dfs_up(int u, int fa) {
    for (auto &edge : g[u]) {
        int v = edge.to;
        double w = edge.w;
        if (v == fa) continue;
        
        // 计算 E_u（从 u 出发，不包含 v 方向）
        double sum = 0.0;
        int cnt = 0;
        
        // 加上其他子节点的贡献
        for (auto &e2 : g[u]) {
            int v2 = e2.to;
            double w2 = e2.w;
            if (v2 == fa) continue;
            if (v2 == v) continue;
            sum += down[v2] + w2;
            cnt++;
        }
        
        // 加上父节点的贡献（如果 u 不是根）
        if (fa != -1) {
            sum += up[u] + w;  // 注意：这里的 w 是 u 到其父节点的边权
            cnt++;
        }
        
        if (cnt > 0) {
            up[v] = w + sum / cnt;
        } else {
            up[v] = w;  // 只有一条路
        }
        
        dfs_up(v, u);
    }
}

3. 计算从每个点出发的总期望

对于节点 $u$：

• 如果 $u$ 是起点：有 $deg[u]$ 个方向可选
• 每个方向的概率为 $\frac{1}{deg[u]}$

总期望：

$$E[u] = \frac{\sum_{v \in neighbor(u)} (从 v 方向走的期望)}{deg[u]} $$

其中：

• 如果 $v$ 是子节点：期望 = $down[v] + w_{u,v}$
• 如果 $v$ 是父节点：期望 = $up[u] + w_{u,fa[u]}$

double calc_expect(int u, int fa) {
    double sum = 0.0;
    for (auto &edge : g[u]) {
        int v = edge.to;
        double w = edge.w;
        if (v == fa) {
            sum += up[u] + w;
        } else {
            sum += down[v] + w;
        }
    }
    return sum / g[u].size();
}

4. 最终答案（树的情况）

$$ans = \frac{\sum_{i=1}^n E[i]}{n}$$

---

第二部分：基环树的情况（$m = n$）

基环树 = 一个环 + 若干棵外向树（挂在环上的树）

1. 找环

使用拓扑排序或 DFS 找出环上的节点。

vector<int> find_cycle() {
    vector<int> deg(n+1, 0);
    for (int u = 1; u <= n; u++) {
        deg[u] = g[u].size();
    }
    
    queue<int> q;
    for (int u = 1; u <= n; u++) {
        if (deg[u] == 1) q.push(u);
    }
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto &edge : g[u]) {
            int v = edge.to;
            if (--deg[v] == 1) {
                q.push(v);
            }
        }
    }
    
    vector<int> cycle;
    vector<bool> in_cycle(n+1, false);
    for (int u = 1; u <= n; u++) {
        if (deg[u] > 1) {
            cycle.push_back(u);
            in_cycle[u] = true;
        }
    }
    return cycle;
}

2. 处理外向树

对于每个环上节点 $u$，处理其子树部分（不包括环上其他节点）：

• 计算 $down[u]$（只往子树方向）
• 这部分和树的情况完全一样

3. 处理环上节点

设环上有 $k$ 个节点：$c_1, c_2, ..., c_k$

对于环上节点 $c_i$，有两个环上邻居：$c_{i-1}$ 和 $c_{i+1}$（环状）

从 $c_i$ 出发，有几种情况：

1. 走向子树方向（已经由 $down[c_i]$ 计算）
2. 沿着环顺时针走
3. 沿着环逆时针走

设：

• $f[i][0]$：从 $c_i$ 出发，沿着环顺时针走的期望
• $f[i][1]$：从 $c_i$ 出发，沿着环逆时针走的期望

计算 $f[i][0]$： 从 $c_i$ 走到 $c_{i+1}$（边权 $w1$），然后：

• 有 $\frac{1}{deg[c_{i+1}]}$ 的概率走向 $c_{i+1}$ 的子树（期望 $down[c_{i+1}]$）
• 有 $\frac{1}{deg[c_{i+1}]}$ 的概率继续顺时针走（期望 $f[i+1][0]$）
• 有 $\frac{deg[c_{i+1}]-2}{deg[c_{i+1}]}$ 的概率走向其他方向（如果有）

更精确地： 设 $c_{i+1}$ 的度数为 $d$，则：

• 有 $\frac{1}{d}$ 的概率走向 $c_i$（来的方向，已访问）
• 有 $\frac{1}{d}$ 的概率走向 $c_{i+2}$（继续顺时针）
• 有 $\frac{d-2}{d}$ 的概率走向子树

因此：

$$f[i][0] = w1 + \frac{down[c_{i+1}] \times (d-2) + f[i+1][0]}{d-1} $$

边界条件：当走到环的起点时，不能继续沿环走。

实际上，我们可以建立方程求解环上的 $f$ 值。

4. 计算环上节点的总期望

对于环上节点 $c_i$，有 $deg[c_i]$ 个方向：

• 子树方向：有 $(deg[c_i]-2)$ 个（因为有两个环上邻居）
• 顺时针方向：1 个
• 逆时针方向：1 个

总期望：

$$E[c_i] = \frac{(down[c_i] \times (deg[c_i]-2) + f[i][0] + f[i][1])}{deg[c_i]} $$

5. 计算最终答案

$$ans = \frac{\sum_{u=1}^n E[u]}{n}$$

---

代码实现框架

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100010;

struct Edge {
    int to;
    double w;
};

int n, m;
vector<Edge> g[MAXN];
vector<int> cycle;
bool in_cycle[MAXN];

// 树的情况
double down[MAXN], up[MAXN];
double expect[MAXN];

// 环的情况
double f[MAXN][2]; // 0:顺时针, 1:逆时针
double cycle_expect[MAXN];

// 找环
vector<int> find_cycle() {
    vector<int> deg(n+1, 0);
    for (int u = 1; u <= n; u++) {
        deg[u] = g[u].size();
    }
    
    queue<int> q;
    for (int u = 1; u <= n; u++) {
        if (deg[u] == 1) q.push(u);
    }
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto &edge : g[u]) {
            int v = edge.to;
            if (--deg[v] == 1) {
                q.push(v);
            }
        }
    }
    
    vector<int> cyc;
    for (int u = 1; u <= n; u++) {
        if (deg[u] > 1) {
            cyc.push_back(u);
            in_cycle[u] = true;
        }
    }
    return cyc;
}

// 计算 down[u]（不走向环上其他点）
void dfs_down(int u, int fa) {
    int cnt = 0;
    double sum = 0.0;
    for (auto &edge : g[u]) {
        int v = edge.to;
        double w = edge.w;
        if (v == fa || in_cycle[v]) continue;
        dfs_down(v, u);
        cnt++;
        sum += down[v] + w;
    }
    if (cnt > 0) {
        down[u] = sum / cnt;
    } else {
        down[u] = 0.0;
    }
}

// 树的情况：计算 up[u]
void dfs_up(int u, int fa) {
    for (auto &edge : g[u]) {
        int v = edge.to;
        double w = edge.w;
        if (v == fa) continue;
        
        double sum = 0.0;
        int cnt = 0;
        
        for (auto &e2 : g[u]) {
            int v2 = e2.to;
            double w2 = e2.w;
            if (v2 == fa) continue;
            if (v2 == v) continue;
            sum += down[v2] + w2;
            cnt++;
        }
        
        if (fa != -1) {
            sum += up[u] + w;
            cnt++;
        }
        
        if (cnt > 0) {
            up[v] = w + sum / cnt;
        } else {
            up[v] = w;
        }
        
        dfs_up(v, u);
    }
}

// 树的情况：计算期望
double calc_expect_tree(int u, int fa) {
    double sum = 0.0;
    for (auto &edge : g[u]) {
        int v = edge.to;
        double w = edge.w;
        if (v == fa) {
            sum += up[u] + w;
        } else {
            sum += down[v] + w;
        }
    }
    return sum / g[u].size();
}

// 处理基环树
void solve_cycle_tree() {
    // 1. 找环
    cycle = find_cycle();
    int k = cycle.size();
    
    // 2. 处理外向树
    for (int u : cycle) {
        dfs_down(u, -1);
    }
    
    // 3. 处理环上的期望
    // 预处理环上边权
    vector<double> w_forward(k), w_backward(k);
    for (int i = 0; i < k; i++) {
        int u = cycle[i];
        int v_next = cycle[(i+1)%k];
        int v_prev = cycle[(i-1+k)%k];
        
        // 找到边权
        for (auto &edge : g[u]) {
            if (edge.to == v_next) w_forward[i] = edge.w;
            if (edge.to == v_prev) w_backward[i] = edge.w;
        }
    }
    
    // 计算环上每个点两个方向的期望
    // 这里需要解方程，简化：用迭代法近似
    for (int i = 0; i < k; i++) {
        f[i][0] = f[i][1] = 0.0;
    }
    
    // 迭代计算
    for (int iter = 0; iter < 100; iter++) {
        for (int i = 0; i < k; i++) {
            int nxt = (i+1) % k;
            int prv = (i-1+k) % k;
            
            double d_next = g[cycle[nxt]].size();
            double d_prev = g[cycle[prv]].size();
            
            // 顺时针
            f[i][0] = w_forward[i] + (down[cycle[nxt]] * (d_next-2) + f[nxt][0]) / (d_next-1);
            
            // 逆时针
            f[i][1] = w_backward[i] + (down[cycle[prv]] * (d_prev-2) + f[prv][1]) / (d_prev-1);
        }
    }
    
    // 4. 计算每个点的期望
    double total_expect = 0.0;
    
    // 环上节点
    for (int i = 0; i < k; i++) {
        int u = cycle[i];
        double d = g[u].size();
        expect[u] = (down[u] * (d-2) + f[i][0] + f[i][1]) / d;
        total_expect += expect[u];
    }
    
    // 非环节点（外向树中的节点）
    // 需要从环上节点开始向外计算
    // 类似树的情况，但根在环上
    // 这里省略具体实现...
    
    // 最终答案
    printf("%.8f\n", total_expect / n);
}

// 处理树
void solve_tree() {
    // 任选根节点
    int root = 1;
    
    // 第一次 DFS：计算 down[]
    dfs_down(root, -1);
    
    // 第二次 DFS：计算 up[]
    up[root] = 0.0;
    dfs_up(root, -1);
    
    // 计算每个点的期望
    double total_expect = 0.0;
    for (int u = 1; u <= n; u++) {
        expect[u] = calc_expect_tree(u, -1);
        total_expect += expect[u];
    }
    
    printf("%.8f\n", total_expect / n);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int x, y, w;
        scanf("%d%d%d", &x, &y, &w);
        g[x].push_back({y, (double)w});
        g[y].push_back({x, (double)w});
    }
    
    if (m == n-1) {
        solve_tree();
    } else {
        solve_cycle_tree();
    }
    
    return 0;
}

---

复杂度分析

树的情况：

• 两次 DFS：$O(n)$
• 总复杂度：$O(n)$

基环树情况：

• 找环：$O(n)$
• 处理外向树：$O(n)$
• 处理环：环大小 $\le 20$，迭代计算 $O(k \cdot iter)$
• 总复杂度：$O(n)$

---

注意事项

1. 精度问题：使用 double 存储，输出时保留足够小数位
2. 边界情况：
   • 度数为 1 的节点（叶子）
   • 度数为 2 的节点（链上）
   • 环的大小为 1 或 2 的特殊情况
3. 除零问题：注意分母为 0 的情况

---

总结

本题是一道典型的概率期望 + 基环树问题，解题步骤：

1. 判断图类型：树 or 基环树
2. 树的情况：
   • 计算向下期望 $down[u]$
   • 换根计算向上期望 $up[u]$
   • 计算总期望
3. 基环树情况：
   • 找环
   • 处理外向树（同树）
   • 处理环上节点的双向期望
   • 综合计算

关键点在于利用基环树的结构特点，分别处理树部分和环部分，最后合并结果。