信奥赛C++提高组 CSP-S 树上前缀和

树上前缀和原理与应用

1、树上前缀和是什么及其作用

树上前缀和是普通前缀和在树形结构上的扩展，主要用于高效处理树上路径的查询问题。

主要作用：

• 快速计算树上任意两点路径上的节点权值和
• 支持快速查询子树和
• 结合树上差分处理路径修改问题
• 降低路径查询的时间复杂度（从 O(n) 降到 O(1) 或 O(log n)，配合 LCA）

2、树上前缀和原理

基本思想：

对于一棵树，我们可以定义两种前缀和：

1. 节点到根的前缀和：sum[u] 表示从根节点到 u 路径上所有节点的权值之和
2. 子树前缀和：sum_sub[u] 表示以 u 为根的子树中所有节点的权值之和

路径和计算公式：

对于任意两点 u 和 v，设它们的最近公共祖先为 lca，则 u 到 v 路径上的节点权值和可以通过以下公式计算：

PathSum(u, v) = sum[u] + sum[v] - 2 * sum[lca] + val[lca]

其中 val[lca] 为最近公共祖先节点的权值，避免被重复减去。该公式利用容斥原理，将路径拆分为两条从根出发的路径并去除重叠部分。