树的统计题解

思路

树上两点之间的简单路径可能跨过许多分叉。若每次询问都重新寻找整条路径，单次操作需要线性时间，无法承受大量操作。需要把树上路径拆成少量连续区间，再用支持单点修改和区间查询的数据结构维护这些区间。

先进行第一次深度优先遍历，求出每个节点的父亲、深度、子树大小和重儿子。对每个非叶节点，选择子树大小最大的儿子作为重儿子，其余儿子为轻儿子。

第二次遍历按重儿子优先的顺序给节点编号。每条重链在新编号中对应一个连续区间。任意根到节点的路径每经过一条轻边，所在子树大小至少减半，因此一条任意路径只会被拆成 $O(\log n)$ 段重链区间。

在新编号序列上建立线段树，每个区间同时维护权值和与权值最大值。单点修改对应线段树上的单点修改。查询 $u$ 到 $v$ 时，只要两点不在同一条重链，就让链顶较深的节点向其链顶父亲跳转，并查询这段连续区间；两点进入同一条重链后，再查询两者编号之间的最后一个区间。

做法

1. 第一次遍历计算父亲、深度、子树大小与重儿子。
2. 第二次遍历优先访问重儿子，记录每个节点的链顶与新编号。
3. 按新编号建立同时维护区间和、区间最大值的线段树。
4. CHANGE 对对应新编号执行单点赋值；路径询问反复处理链顶较深的一段，最后处理同链区间并合并结果。

所有路径和使用 64 位有符号整数保存；路径最大值以小于所有合法点权的值初始化。

证明

第一次遍历为每个节点确定唯一的重儿子，因此第二次遍历把每条重链上的节点连续编号。线段树对任意一个重链区间返回的和与最大值，正好等于该区间所含树节点的权值和与最大值。

路径查询过程中，当两点链顶不同时，链顶较深的一侧从当前节点到该链顶的整段都位于目标简单路径上。把这一段计入答案后，将该侧节点移动到链顶父亲，不会遗漏或重复任何路径节点。每次移动都会跨过一条轻边。最终两点位于同一重链，此时两者编号之间的连续区间恰好是尚未处理的路径部分。各段互不相交且并集为原路径，所以累加得到正确的路径和，逐段取最大值得到正确的路径最大值。

单点修改只改变一个节点在新编号序列中的对应位置。线段树修改后，所有包含该位置的区间信息都会更新，因此后续查询使用的每个区间统计均与当前权值一致。

复杂度

两次遍历和建树需要 $O(n)$ 时间与 $O(n)$ 空间。一次单点修改需要 $O(\log n)$ 时间；一条路径被拆成 $O(\log n)$ 段，每段线段树查询需要 $O(\log n)$ 时间，因此一次路径询问需要 $O(\log^2 n)$ 时间。总空间复杂度为 $O(n)$。