题解：Slučajna Cesta

题目分析

问题核心

给定一棵有 (n) 个节点的树（公园），每个节点有美丽值 (v_i)。每条边独立随机为蓝蛇（禁止小→大方向）或红蛇（禁止大→小方向），概率各为 (\frac{1}{2})。Vito 从节点 (i) 出发，仅沿安全边（不被蛇攻击）随机行走（等概率选择安全边），直到无安全边停止。求路线美感（经过节点的美丽值之和，重复经过多次则多次计算）的期望，结果对 (10^9+7) 取模（分数用逆元表示）。

关键观察与建模

1. 边的方向约束：
   • 边 (u-v)（假设 (u < v)）：蓝蛇时仅允许 (v→u)，红蛇时仅允许 (u→v)。
   • 每条边的方向是确定的（二选一），且独立于其他边。
2. 行走规则：
   • 每次从当前节点选择所有安全边，等概率随机选择一条继续行走。
   • 无安全边时停止，路线美感为所有经过节点的美丽值之和（含起点）。
3. 期望的线性性质：
   • 路线美感的期望 = 每个节点 (x) 被经过的期望次数 × (v_x) 之和。
   • 核心简化：只需计算每个节点 (x) 对起点 (i) 的“被经过期望次数”，再加权求和。

核心公式推导

1. 单节点的期望经过次数

设 (E(i, x)) 为从 (i) 出发，节点 (x) 被经过的期望次数。则总期望为： [ \text{ans}(i) = \sum_{x=1}^n E(i, x) \cdot v_x ]

• 起点 (i) 的初始次数为 1，即 (E(i, i) \geq 1)。
• 若从 (x) 能走到 (y)，则 (E(i, y)) 包含 (E(i, x) \cdot \text{Prob}(x→y))（(\text{Prob}(x→y)) 为从 (x) 走到 (y) 的概率）。

2. 树结构下的期望简化

树的无环特性导致：从节点 (x) 出发，仅能向“父节点”或“子节点”方向行走（取决于边的方向）。结合边的随机性，可推导出：

• 对于节点 (x) 的子树，每条边的方向选择独立，且对期望的贡献可通过组合数学计算（如 (2^k) 种方向组合）。
• 关键公式：节点 (x) 的期望贡献可表示为 (v_x + \sum_{y \in \text{children}(x)} \frac{1}{2} \cdot E(y, x) \cdot \text{系数})，其中系数与子树大小相关。

数据范围挑战

• (n \leq 10^6)，需设计 (O(n)) 复杂度的线性算法，避免递归或高次运算。
• 核心难点：高效计算每个节点的期望贡献，利用预处理的阶乘、逆元优化分数运算。

算法设计

核心思路

1. 预处理：提前计算 (2^k \mod \text{mod})、逆元、逆 (2^k) 等，用于快速计算组合数和分数。
2. 树形 DP（后序遍历）：计算每个节点 (x) 作为“根”时，其子树对自身期望的贡献（记为 (f[x])）。
3. 换根 DP（前序遍历）：将根从父节点转移到子节点，计算每个节点作为起点时的总期望（记为 (g[x])），即最终答案。

具体步骤

1. 预处理（init 函数）

• (fac2[i] = 2^i \mod \text{mod})：用于计算边的方向组合数。
• (inv2[i] = (2^i)^{-1} \mod \text{mod})：用于计算概率中的 (\frac{1}{2^i})。
• (inv[i] = i^{-1} \mod \text{mod})：用于计算分数除法（如 (\frac{1}{k})）。

2. 辅助函数

• (cal(x))：计算 (\frac{2^x - 1}{x} \mod \text{mod})（组合数学中的关键系数，推导自期望的线性性质）。
• (get_val(u, cnt, sum))：计算节点 (u) 的期望贡献，其中 (cnt) 是子节点数，(sum) 是子节点期望贡献之和。公式为： [ get_val(u, cnt, sum) = v[u] + \frac{1}{2^{cnt}} \cdot \frac{2^{cnt} - 1}{cnt} \cdot sum \mod \text{mod} ] （简化后通过预处理的逆元快速计算）。

3. 后序遍历（计算 (f[x])）

• 遍历顺序：从叶子节点到根节点（节点编号从 (n) 到 (1)）。
• 逻辑：对于每个节点 (x)，累加其子节点的 (f[y]) 之和（(sum[fa[x]])），统计子节点数（(son[fa[x]])），并通过 (get_val) 计算 (f[x])。

4. 前序遍历（计算 (g[x])，换根 DP）

• 遍历顺序：从根节点到叶子节点（节点编号从 (1) 到 (n)）。
• 逻辑：对于每个节点 (x)，将父节点 (fa[x]) 的期望贡献转移到 (x)，更新 (x) 的总期望 (g[x])：
  • 父节点的贡献需排除 (x) 本身的贡献（避免重复计算）。
  • 利用换根公式，将父节点的期望 (g[fa[x]]) 转化为 (x) 的额外贡献，再结合 (f[x]) 得到总期望。

关键公式推导

1. 后序遍历 (f[x])

(f[x]) 表示节点 (x) 作为根时，仅考虑子树的期望贡献： [ f[x] = v[x] + \frac{2^{k} - 1}{k \cdot 2^{k}} \cdot \sum_{y \in \text{children}(x)} f[y] ] 其中 (k) 是 (x) 的子节点数。推导依据：

• 每个子节点与 (x) 的边有 (2) 种方向，共 (2^k) 种组合。
• 仅当边的方向允许从 (x) 到子节点 (y) 时，(y) 的贡献才会传递到 (x)，概率为 (\frac{1}{2})。
• 组合系数 (\frac{2^k - 1}{k}) 来自所有非空方向组合的平均贡献。

2. 换根 DP (g[x])

(g[x]) 表示节点 (x) 作为起点时的总期望，需考虑父节点所在的“上部子树”贡献： [ g[x] = v[x] + \frac{2^{k'} - 1}{k' \cdot 2^{k'}} \cdot \left( \sum_{y \in \text{children}(x)} f[y] + F \right) ] 其中 (k' = k + 1)（父节点视为 (x) 的额外子节点），(F) 是父节点传递的贡献（排除 (x) 本身的贡献）。

代码关键模块解析

1. 预处理（init 函数）

void init() {
    fac2[0] = 1;
    for (int i = 1; i <= n; ++i)
        fac2[i] = mul(fac2[i - 1], 2); // 2^i mod mod
    inv2[n] = fpow(fac2[n], mod - 2);
    for (int i = n; i; --i)
        inv2[i - 1] = mul(inv2[i], 2); // (2^(i-1))^{-1} mod mod
    inv[0] = inv[1] = 1;
    for (int i = 2; i <= n; ++i)
        inv[i] = mul(mod - mod / i, inv[mod % i]); // 逆元（费马小定理）
}

• 预处理的核心是避免重复计算，确保每个分数运算均可在 (O(1)) 时间完成。

2. 辅助函数

inline int cal(int x) {
    return mul(add(fac2[x], -1), inv[x]); // (2^x - 1)/x mod mod
}
inline int get_val(int u, int cnt, int sum) {
    return add(val[u], mul(inv2[cnt], cal(cnt), sum)); // 节点u的期望贡献
}

• (cal(x)) 是关键系数，推导自期望中“所有非空方向组合的平均贡献”。
• (get_val) 整合了节点自身的美丽值和子节点的期望贡献，体现了后序遍历的核心逻辑。

3. 后序遍历（计算 (f[x])）

for (int i = n; i; --i) {
    f[i] = get_val(i, son[i], sum[i]); // 子节点贡献之和sum[i]，子节点数son[i]
    toadd(sum[fa[i]], f[i]); // 将f[i]累加到父节点的sum中
    ++son[fa[i]]; // 父节点的子节点数+1
}

• 遍历顺序从 (n) 到 (1)，确保处理父节点前已处理所有子节点。
• (sum[fa[i]]) 存储父节点的所有子节点的 (f[y]) 之和，(son[fa[i]]) 存储父节点的子节点数。

4. 前序遍历（计算 (g[x])）

for (int i = 1; i <= n; ++i) {
    if (i != 1) {
        // 父节点fa[i]的子节点数（排除i本身）
        int fson = son[fa[i]] - (fa[i] == 1);
        // 父节点的期望贡献（排除i的贡献）
        int F = get_val(fa[i], fson, add(whole[fa[i]], -f[i]));
        int newson = son[i] + 1; // 换根后i的子节点数（原父节点+原子节点）
        whole[i] = add(sum[i], F); // i的总贡献（子节点+父节点）
        g[i] = get_val(i, newson, whole[i]); // 换根后的总期望
    } else {
        g[i] = f[i]; // 根节点无父节点，f[i]即为总期望
        whole[i] = sum[i]; // 根节点的总贡献=子节点贡献之和
    }
}

• 换根逻辑：将父节点视为子节点，重新计算当前节点的子节点数和总贡献。
• (F) 是父节点排除当前节点后的期望贡献，确保换根时不重复计算。

时间复杂度与空间复杂度

• 时间复杂度：(O(n))。预处理、后序遍历、前序遍历均为线性时间，每个节点仅处理一次。
• 空间复杂度：(O(n))。存储预处理数组（(fac2)、(inv)、(inv2)）、DP数组（(f)、(g)）、辅助数组（(sum)、(son)、(whole)），均为线性空间。

关键结论

1. 期望的线性性质：将总期望拆分为每个节点的期望经过次数与美丽值的乘积之和，简化问题。
2. 树形 DP + 换根 DP：后序遍历计算子树贡献，前序遍历扩展到全树，实现 (O(n)) 复杂度。
3. 预处理优化：利用模运算的逆元、快速幂，高效处理分数运算（如 (\frac{2^k - 1}{k \cdot 2^k})），适配大规模数据。