🧩 问题核心与性质分析

题目描述了一个由 $n$ 个充电元件和 $n-1$ 条导线构成的树形结构。每个元件有直接充电概率 $q_i$，每条导线有导电概率 $p$。电能可以从直接充电的元件通过通电的导线间接传播。

我们需要计算进入充电状态的元件个数的期望值。

根据期望的线性性质，元件个数的期望等于每个元件充电概率之和：

$$E[\text{充电元件个数}] = \sum_{i=1}^n P(i)$$

其中 $P(i)$ 表示元件 $i$ 充电的概率。

因此，问题转化为计算每个元件被充电的概率。

💡 概率计算与树形DP

由于电能传播具有树形结构和方向性，我们需要考虑概率的联合作用。一个元件充电当且仅当：

• 它自身直接充电，或者
• 通过导电的导线从某个已充电的邻居获得电能

🔹 第一步：定义状态

设：

• $f[u]$：在以 $u$ 为根的子树中，$u$ 不充电的概率
• $g[u]$：考虑整棵树时，$u$ 不充电的概率

🔹 第二步：自底向上计算（子树贡献）

对于叶子节点 $u$，$f[u] = 1 - q_u$（即不自身充电的概率）。

对于非叶子节点 $u$，考虑其子节点 $v$ 和连接边 $(u,v)$ 的导电概率 $p$：

• 如果边不通电（概率 $1-p$），则 $v$ 对 $u$ 无影响
• 如果边通电（概率 $p$），则要求 $v$ 所在的子树不能使 $u$ 充电，即 $v$ 不充电的概率为 $f[v]$

因此，$v$ 不使 $u$ 充电的概率为：$(1-p) + p \times f[v]$

所有子节点都不使 $u$ 充电的概率是它们各自概率的乘积：

$$f[u] = (1 - q_u) \times \prod_{v \in \text{children}(u)} \big[(1-p) + p \times f[v]\big] $$

🔹 第三步：自顶向下计算（父节点影响）

现在考虑父节点对当前节点的影响。

设 $g[u]$ 表示考虑整棵树时 $u$ 不充电的概率。

对于根节点，$g[\text{root}] = f[\text{root}]$。

对于非根节点 $u$，其父节点为 $fa$：

父节点 $fa$ 对 $u$ 的影响需要考虑：去掉 $u$ 的贡献后，$fa$ 不充电的概率，记为 $t$。

根据 $f[fa]$ 的计算式：

$$f[fa] = (1 - q_{fa}) \times \prod_{v \in \text{children}(fa)} \big[(1-p) + p \times f[v]\big] $$

去掉 $u$ 的贡献：

$$t = \frac{f[fa]}{(1-p) + p \times f[u]}$$

这里需要特判分母为0的情况，此时 $t = 0$。

然后，考虑父节点的影响传递到 $u$：

• 边 $(fa,u)$ 不通电（概率 $1-p$），则父节点无影响
• 边 $(fa,u)$ 通电（概率 $p$），则要求父节点（去掉 $u$ 后）不充电的概率为 $t$

因此，父节点不使 $u$ 充电的概率为：$(1-p) + p \times t$

最终，$u$ 不充电的概率为：

$$g[u] = f[u] \times \big[(1-p) + p \times t\big]$$

🔹 第四步：计算答案

每个节点 $u$ 充电的概率为 $1 - g[u]$，因此答案为：

$$\text{ans} = \sum_{u=1}^n (1 - g[u])$$

🧮 算法实现细节

伪代码

function solve():
    读取 n
    构建图，存储边和导电概率
    读取每个节点的直接充电概率 q[i]
    
    # 第一遍DFS：自底向上计算f[u]
    function dfs1(u, parent):
        f[u] = 1 - q[u]  # 初始化为自身不充电的概率
        for each v in neighbors(u) where v ≠ parent:
            dfs1(v, u)
            p = 边(u,v)的导电概率
            f[u] *= (1-p) + p * f[v]
    
    # 第二遍DFS：自顶向下计算g[u]  
    function dfs2(u, parent):
        ans += 1 - g[u]  # 累加u的充电概率
        
        # 预处理子节点列表和前缀后缀积
        children = []
        for v in neighbors(u) where v ≠ parent:
            children.append(v)
        
        # 计算前缀积和后缀积
        pre[0] = 1
        for i = 0 to len(children)-1:
            v = children[i]
            p = 边(u,v)的导电概率
            pre[i+1] = pre[i] * ((1-p) + p * f[v])
        
        suf[len(children)] = 1
        for i = len(children)-1 down to 0:
            v = children[i]  
            p = 边(u,v)的导电概率
            suf[i] = suf[i+1] * ((1-p) + p * f[v])
        
        # 计算每个子节点的t值并递归
        for i = 0 to len(children)-1:
            v = children[i]
            p = 边(u,v)的导电概率
            
            # 计算去掉v后u不充电的概率
            t = g[u] * pre[i] * suf[i+1]
            if (1-p) + p * f[v] > 1e-9:  # 避免除0
                t = t / ((1-p) + p * f[v])
            
            # 计算v的不充电概率g[v]
            g[v] = f[v] * ((1-p) + p * t)
            dfs2(v, u)

⚠️ 注意事项

1. 精度处理：概率计算使用 double 类型，比较时使用容差（如 1e-9）
2. 除零保护：计算 $t$ 值时需要判断分母是否为0
3. 树根选择：可以任意选择节点1作为根节点
4. 数值稳定性：概率连乘可能产生数值下溢，必要时可取对数

💎 总结

这道题的核心是树形概率DP，通过两次DFS遍历：

• 第一次DFS：自底向上计算子树内的概率
• 第二次DFS：自顶向下计算整棵树的概率

关键技巧在于：

• 利用期望线性性质将问题转化为求每个元件充电概率
• 通过去除贡献的方法计算父节点对当前节点的影响
• 使用前缀后缀积优化计算，避免重复遍历

该算法的时间复杂度为 $O(n)$，适合 $n \leq 500000$ 的数据规模。