题目理解

我们有一棵 $n$ 个节点的树，初始时每个节点上有一个数字 $123456789123456789$。

有两种操作：

1. 修改操作：给 $s$ 到 $t$ 路径上的每个点 $r$ 添加一个数字 $a \cdot \mathrm{dis}(s, r) + b$
2. 查询操作：查询 $s$ 到 $t$ 路径上所有点上的所有数字的最小值

其中 $\mathrm{dis}(s, r)$ 表示 $s$ 到 $r$ 的距离。

---

问题分析

1. 操作的本质

修改操作实际上是在路径上添加一个线性函数：

• 对于路径上的点 $r$，添加 $f(r) = a \cdot d + b$，其中 $d = \mathrm{dis}(s, r)$

查询操作要求：$\min\limits_{r \in path(s,t)} \min\{\text{所有在r上的数字}\}$

2. 关键观察

在树路径 $s \to t$ 上，距离函数 $\mathrm{dis}(s, r)$ 是分段线性的：

• 设 $L = \mathrm{LCA}(s, t)$，路径分为 $s \to L$ 和 $L \to t$ 两段
• 在 $s \to L$ 段：$\mathrm{dis}(s, r)$ 单调递增
• 在 $L \to t$ 段：$\mathrm{dis}(s, r) = \mathrm{dis}(s, L) + \mathrm{dis}(L, r)$，也是线性函数

因此，整个路径上的 $f(r) = a \cdot \mathrm{dis}(s, r) + b$ 实际上是两段线性函数。

---

算法设计

方法：树链剖分 + 李超线段树

1. 树链剖分

• 将树分解为 $O(\log n)$ 条重链
• 每条重链在 DFS 序上是连续的区间

2. 李超线段树

• 每个节点维护当前区间内最低的线段
• 支持区间插入线段、区间查询最小值

3. 操作实现

修改操作 $(s, t, a, b)$：

1. 计算 $L = \mathrm{LCA}(s, t)$
2. 将路径 $s \to t$ 拆分为 $s \to L$ 和 $L \to t$
3. 对于每段，在树剖对应的区间上插入线性函数

查询操作 $(s, t)$：

1. 同样拆分为 $s \to L$ 和 $L \to t$
2. 在树剖对应的区间上查询最小值
3. 取所有区间的最小值

---

具体实现细节

1. 线性函数表示

对于函数 $f(x) = kx + b$，其中 $x$ 是 DFS 序位置对应的到根节点的距离。

在路径 $s \to L$ 上：

• $x = \mathrm{dis}(root, r)$
• $f(x) = a \cdot (\mathrm{dis}(root, r) - \mathrm{dis}(root, s)) + b$
• 化简得：$f(x) = a \cdot x + (b - a \cdot \mathrm{dis}(root, s))$

在路径 $L \to t$ 上：

• $f(x) = a \cdot (\mathrm{dis}(s, L) + \mathrm{dis}(L, r)) + b$
• $= a \cdot x + (b + a \cdot (\mathrm{dis}(s, L) - \mathrm{dis}(root, L)))$

2. 李超线段树节点

struct Node {
    ll k, b;  // 线段: k*x + b
    ll min_val;  // 区间最小值
    int l, r;
};

插入线段时，比较当前线段与节点中线段的优劣，选择更小的。

3. 复杂度分析

• 树链剖分：$O(\log n)$ 条链
• 李超线段树：每次插入 $O(\log^2 n)$，查询 $O(\log^2 n)$
• 总复杂度：$O(m \log^3 n)$（勉强可过）

---

优化技巧

1. 标记永久化

李超线段树可以使用标记永久化，避免下传标记的开销。

2. 区间查询优化

查询时直接遍历所有相关区间，而不是合并区间。

3. 常数优化

• 使用 DFS 序的连续性
• 避免递归过深

---

样例验证

输入：

3 5
1 2 10
2 3 20
2 1 3
1 2 3 5 6
2 2 3
1 2 3 -5 -6
2 2 3

分析：

1. 初始所有点值为 $123456789123456789$
2. 第一次查询：输出初始值
3. 插入 $5 \cdot \mathrm{dis} + 6$：
   • 路径 $2 \to 3$：点2添加6，点3添加 $5\times20+6=106$
   • 最小值6
4. 插入 $-5 \cdot \mathrm{dis} - 6$：
   • 点2添加 $-5\times0-6=-6$，点3添加 $-5\times20-6=-106$
   • 最小值 $-106$

输出：

123456789123456789
6
-106

符合样例。

---

总结

本题的关键在于：

1. 将路径添加数字转化为插入线性函数
2. 利用树链剖分将路径操作转化为区间操作
3. 使用李超线段树维护区间最小线段
4. 注意距离函数的变换和分段处理

算法复杂度 $O(m \log^3 n)$，在 $n, m \leq 10^5$ 时经过优化可以通过。