树中的排他和计算：能否通过预处理实现O(|K|)复杂度求解？

首先明确核心问题：你需要的排他和，本质是每个节点的累计和，减去集合K中离它最近的那个祖先节点的累计和（如果集合里没有它的祖先，就直接用自身的累计和）。之所以不用减更上层的祖先，是因为最近祖先的累计和已经包含了所有上层祖先的数值贡献，重复减会导致计算错误。

预处理方案（O(N logN) 时间/空间） #

要实现快速查询每个节点在K中的最近祖先，我们可以用倍增法预处理节点的祖先信息，这是处理树/内向DAG祖先查询的经典优化手段：

1. 计算节点深度：通过DFS或拓扑排序遍历，给每个节点标记深度（根节点深度为0，子节点深度比父节点大1）。
2. 构建倍增表：
   • 先记录每个节点的直接父节点（最多2个），存在up[0][u]数组里（如果只有1个父节点，另一个位置设为null或根节点）。
   • 对于k ≥ 1，up[k][u]表示节点u的第2^k级祖先（比如up[1][u]是u的祖父节点），通过up[k-1][up[k-1][u]]递推生成，直到覆盖最大深度的节点。

每组K集合的处理（O(|K| logN) 时间） #

有了预处理的倍增表，每组K的处理可以快速完成：

1. 把K中的节点存入哈希集合，方便O(1)判断某个节点是否在集合里。
2. 对K中的每个节点u：
   a. 初始化最近祖先为null，最大深度为-1。
   b. 遍历u的每个父节点（1或2个），用倍增法向上查找该路径上第一个属于K的节点：
   • 从最大的k值开始尝试跳步，如果跳步后的节点不在K中，就跳到该节点继续查找；如果在K中，就缩小k值尝试更短的跳步，直到找到离u最近的那个祖先。
     c. 在所有父节点路径找到的候选祖先中，选深度最大的那个（也就是离u最近的）。
     d. 计算排他和：如果找到最近祖先，就是cumsum(u) - cumsum(最近祖先)；如果没找到，直接用cumsum(u)。

为什么这个方案高效？ #

倍增法的每次查询只需要O(logN)时间，而logN的值通常很小（比如N=1e5时，logN≈17），实际处理效率几乎和O(|K|)持平。相比O(N)的DFS或O(|K|²)的暴力对比，这个方案能轻松应对多组K集合的场景，即使K规模较大也能快速处理。

内容的提问来源于stack exchange，提问作者Richard