问题分析

给定一棵 $N$ 个节点的树，每个节点 $i$ 有一个宝石价格 $p_i$。有 $Q$ 次操作，每次操作给出 $a, b, v$，表示：

查询从 $a$ 到 $b$ 的路径上，最大利润（即路径上某个点买入、后面某个点卖出的最大差价）

将 $a$ 到 $b$ 路径上所有节点的宝石价格增加 $v$

算法思路

核心数据结构：树链剖分 + 线段树

使用树链剖分将树转化为线性序列，然后用线段树维护区间信息。

线段树节点设计

每个线段树节点维护以下信息：

$mx$：区间内宝石最高价格

$mn$：区间内宝石最低价格

$u$：区间内正向最大利润（即前面买入、后面卖出）

$d$：区间内反向最大利润（即后面买入、前面卖出）

关键操作

1.信息合并（merge函数）

2.路径更新（U函数）

使用树链剖分将路径拆分成 $O(\log N)$ 条重链区间，在线段树上区间加 $v$。

3.路径查询（Q函数）

分三种情况处理：

情况1：$y$ 是 $x$ 的祖先

从 $x$ 向上走到 $y$，维护正向最大利润

最终返回 $I.u$（正向最大利润）

情况2：$x$ 是 $y$ 的祖先

从 $y$ 向上走到 $x$，但需要反向计算利润

最终返回 $I.d$（反向最大利润）

情况3：一般情况（LCA不是端点）

从 $x$ 向上走到 LCA，计算反向利润

从 LCA 向下走到 $y$，计算正向利润

合并两部分信息，返回 $A.d$

算法流程

1.预处理：

树链剖分（两次DFS）

建立线段树，初始化为各点宝石价格

2.处理每个查询：

查询路径 $a \to b$ 的最大利润

更新路径 $a \to b$ 上所有节点的价格（加 $v$）

复杂度分析

树链剖分：$O(N)$

每次查询/更新：$O(\log^2 N)$（树链剖分 $O(\log N)$ 条链 × 线段树 $O(\log N)$）

总复杂度：$O(N + Q \log^2 N)$

关键技巧

1.双向利润计算：同时维护正向($u$)和反向($d$)最大利润，适应不同方向的路径查询

2.懒标记更新：路径加操作使用懒标记，保证复杂度

3.路径分段处理：利用树链剖分将树上路径转化为 $O(\log N)$ 个区间

总结

本题通过树链剖分+线段树的经典组合，高效解决了树上路径查询和更新问题。关键在于设计合适的数据结构来维护路径上的最大利润信息，并正确处理不同方向的路径查询。算法在 $N, Q \leq 10000$ 的规模下能够高效运行。