问题理解

我们有一棵 $n$ 个节点的树，每个节点有权值 $w_i$。需要支持三种操作：

1. 单点修改：CHANGE u t - 修改节点 $u$ 的权值为 $t$
2. 路径最大值查询：QMAX u v - 查询 $u$ 到 $v$ 路径上的最大权值
3. 路径和查询：QSUM u v - 查询 $u$ 到 $v$ 路径上的权值和

数据规模：$n \leq 3\times 10^4$，$q \leq 2\times 10^5$

---

关键挑战

直接暴力处理路径查询的复杂度是 $O(nq)$，无法接受。
需要将树上的路径问题转化为序列上的区间问题。

---

算法核心：树链剖分

1. 树链剖分思想

将树划分为若干条重链，使得：

• 从根到任意节点的路径最多经过 $O(\log n)$ 条重链
• 每条重链在 DFS 序上是连续的区间

2. 剖分过程

定义：

• 重儿子：节点 $u$ 的所有儿子中子树大小最大的那个
• 重边：连接节点与其重儿子的边
• 重链：由重边连接形成的极大链

预处理步骤：

1. 第一次 DFS：计算子树大小、深度、父节点，确定重儿子
2. 第二次 DFS：优先遍历重儿子，生成 DFS 序，记录：
   • 每个节点所在重链的顶端
   • 节点在 DFS 序中的位置

3. 路径查询转化

对于路径 $(u, v)$ 的查询：

1. 不断将深度较大的点向上跳到所在重链的顶端
2. 每次跳转对应 DFS 序上的一个连续区间
3. 路径被分解为 $O(\log n)$ 个区间

---

数据结构：线段树

维护信息

在 DFS 序列上建立线段树，每个节点维护：

• max_val：区间最大值
• sum：区间和

操作实现

• 单点修改：根据节点在 DFS 序中的位置，在线段树中修改
• 区间查询：对路径分解得到的每个区间分别查询，然后合并结果

---

算法流程

预处理阶段

1. DFS1：计算子树大小、深度、父节点、重儿子
2. DFS2：生成 DFS 序，记录节点位置和重链顶端
3. 建线段树：根据 DFS 序和节点权值建立线段树

查询处理

路径最大值 QMAX(u, v)

1. 初始化 res = -∞
2. 当 $u$ 和 $v$ 不在同一条重链时：
   • 选择深度较大的点（设为 $x$）
   • 查询 $x$ 到其重链顶端的区间最大值，更新 res
   • 将 $x$ 跳到重链顶端的父节点
3. 最后 $u$ 和 $v$ 在同一条重链上，查询它们之间的区间最大值
4. 返回 res

路径和 QSUM(u, v)

与 QMAX 类似，但维护和而不是最大值

单点修改 CHANGE(u, t)

1. 找到节点 $u$ 在 DFS 序中的位置 pos[u]
2. 在线段树中修改 pos[u] 处的值

---

复杂度分析

• 预处理：两次 DFS $O(n)$，建线段树 $O(n)$
• 单次查询/修改：
  • 路径分解：$O(\log n)$ 次跳转
  • 线段树操作：每次 $O(\log n)$
  • 总复杂度：$O(\log^2 n)$
• 总体复杂度：$O(n + q \log^2 n)$，可接受

---

样例分析

样例树：

1(4)
├── 2(2)
│   └── 3(1)
└── 4(3)

第一次查询 QMAX 3 4：

• 路径：3 → 2 → 1 → 4
• 最大值：max(1, 2, 4, 3) = 4

修改 CHANGE 1 5 后：

• 节点1权值变为5

QMAX 3 4：

• 路径：3 → 2 → 1 → 4
• 最大值：max(1, 2, 5, 3) = 5

---

总结

这道题的核心是：

1. 问题转化：将树上路径问题转化为序列区间问题
2. 树链剖分：通过重链划分实现路径的高效分解
3. 线段树应用：在DFS序列上维护区间信息
4. 算法组合：树链剖分 + 线段树的经典组合

通过这种分层处理的方法，可以在对数时间内完成路径查询和单点修改，有效处理大规模数据。