题解：树形概率问题与线段树合并

问题重述

给定一棵二叉树，每个节点有两种可能：
1. 叶子节点：具有一个固定权值
2. 非叶子节点：以概率p选择子节点最大值，以概率1-p选择最小值
求根节点所有可能权值的概率分布，并计算特定加权和

算法核心：动态规划+线段树合并

1. 概率转移方程

对于非叶子节点i和权值j：

f[i][j] = 
    f[left][j] * (p * sum(f[right][<j]) + (1-p) * sum(f[right][>j])) 
  + f[right][j] * (p * sum(f[left][<j]) + (1-p) * sum(f[left][>j]))

2. 线段树优化

• 动态开点线段树：每个节点维护一棵权值线段树
• 合并操作：合并子树线段树时维护概率转移
• 离散化：将大值域压缩到小范围

关键实现

线段树合并核心

int merge(int x, int y, int l, int r, int xmul, int ymul, int v) {
  if (!x && !y) return 0;
  if (!x) { pushmul(y, ymul); return y; }  // 只有y树，直接应用乘法标记
  if (!y) { pushmul(x, xmul); return x; }  // 只有x树，直接应用乘法标记

  pushd(x), pushd(y);  // 下传懒惰标记
  int mid = l + r >> 1;

  // 预处理子树和
  int lsx = sum[ls[x]], lsy = sum[ls[y]], rsx = sum[rs[x]], rsy = sum[rs[y]];

  // 合并左子树：考虑右子树的贡献
  ls[x] = merge(ls[x], ls[y], l, mid, 
               (xmul + 1ll * rsy % mod * (1 - v + mod)) % mod,  // x树乘法标记更新
               (ymul + 1ll * rsx % mod * (1 - v + mod)) % mod, v);  // y树乘法标记更新

  // 合并右子树：考虑左子树的贡献
  rs[x] = merge(rs[x], rs[y], mid + 1, r,
               (xmul + 1ll * lsy % mod * v) % mod,
               (ymul + 1ll * lsx % mod * v) % mod, v);

  pushup(x);  // 更新当前节点信息
  return x;
}

树形DP处理

void dfs(int u) {
  if (is_leaf(u)) {  // 叶子节点初始化
    upd(rt[u], 1, qwq, val[u], 1); 
    return;
  }

  // 递归处理子树
  dfs(left_child);
  dfs(right_child);

  // 合并子树线段树
  rt[u] = merge(rt[left_child], rt[right_child], 1, qwq, 0, 0, val[u]);
}

复杂度分析

• 时间：O(n log C)，C为离散化后的值域大小
• 空间：O(n log C)，动态开点线段树

思考过程

1. 暴力思路：直接枚举所有可能性，O(n^2)不可行
2. DP优化：发现概率可以分解为子问题
3. 数据结构选择：需要高效维护区间和与合并操作
4. 离散化处理：将1e9的值域压缩到1e5级别

样例解释

输入：

3
0 1 1  // 节点1是根，左右孩子为2,3
5000 1 2  // 节点1概率0.5，节点2值1，节点3值2

处理：
1. 离散化：值[1,2] → 排名1,2
2. 概率计算：
• 节点1有50%概率取max(1,2)=2
• 50%概率取min(1,2)=1
3. 结果：概率各0.5，输出加权和

总结

本题展示了如何用线段树合并高效解决树形概率问题，关键点：
1. 将概率转移分解为子问题
2. 用动态数据结构维护值域信息
3. 离散化处理大值域

这种树形DP+线段树合并的思路，适用于许多需要维护值域信息的树形统计问题。