好的，这是该题目的详细文字题解。

---

NOI 2014《购票》题解

问题抽象

我们有一棵以 $1$ 为根、$n$ 个节点的树，每个节点 $v$（除根外）有：

• 父亲 $f_v$
• 到父亲的距离 $s_v$
• 票价参数 $p_v, q_v$
• 距离限制 $l_v$

从 $v$ 到 $1$ 可以分段购票：每次选择 $v$ 的一个祖先 $a$，花费 $p_v \cdot \text{dist}(v,a) + q_v$，但要求 $\text{dist}(v,a) \le l_v$。求每个 $v$ 到 $1$ 的最小总花费。

---

1. 基础定义与 DP 方程

设 $d_u$ 表示 $u$ 到根 $1$ 的距离（边权和，前缀和），可以通过一次 DFS 求出。

设 $dp_u$ 表示从 $u$ 到 $1$ 的最小总花费。对于 $u \neq 1$：

$$dp_u = \min_{a \in \text{anc}(u),\ d_u - d_a \le l_u} \big\{ dp_a + (d_u - d_a) \cdot p_u + q_u \big\} $$

其中 $\text{anc}(u)$ 是 $u$ 的祖先集合（含 $u$ 自身）。

---

2. 公式变形

把常数部分分离：

$$dp_u = \min_{a} \big\{ (dp_a - d_a \cdot p_u) \big\} + d_u \cdot p_u + q_u $$

对于固定的 $u$，我们要在满足 $d_a \ge d_u - l_u$ 的祖先 $a$ 中，最小化：

$$F(a) = dp_a - d_a \cdot p_u$$

记 $x_a = d_a$，$y_a = dp_a$，那么 $F(a) = y_a - p_u \cdot x_a$。
这是一个关于 $p_u$ 的线性函数形式：在二维平面上有若干点 $(x_a, y_a)$，要找一条斜率 $k = p_u$ 的直线 $y = kx + b$ 穿过某点时的截距 $b$ 最小，即 $b = y_a - kx_a$ 最小。

---

3. 几何转化：凸壳维护

在平面上，如果我们有一组点 $(x_i, y_i)$，那么使 $y_i - kx_i$ 最小的点，一定在这些点构成的下凸壳上。

下凸壳性质：按 $x$ 排序后，相邻点连线斜率递增。

查询：给定斜率 $k$，在下凸壳上找到第一个斜率大于 $k$ 的线段左端点，该点即为最优决策点（可二分查找）。

---

4. 距离限制的处理

对于 $u$，合法的 $a$ 需满足 $d_a \ge d_u - l_u$。
因为 $d_a$ 随 $a$ 靠近根而减小，所以这相当于在祖先链上取一个后缀。

因此我们需要在 $u$ 到根的路径上，对 $d_a$ 在某个值以上的祖先点维护凸壳，并支持查询。

---

5. 特殊情况分析

题中 $t$ 参数提示了部分分做法：

• $t=0$ 或 $1$：$l_v$ 极大，无距离限制。此时只需在整条祖先链的凸壳上查询。因为 $f_v = v-1$（链）或任意树但无限制，可以用栈维护凸壳，$O(n \log n)$ 或 $O(n)$（若 $p$ 单调）解决。

• $t=0$ 或 $2$：树是一条链，$f_v = v-1$。祖先链就是 $1,2,\dots,u$。此时 $d$ 单调递增，可以用单调队列维护凸壳，并在队列上二分找到第一个 $d_a \ge d_u - l_u$ 的位置（即满足距离限制的最远祖先），然后在该段凸壳中二分查询。复杂度 $O(n \log n)$。

• $t=3$：一般情况，树形态任意，有距离限制。

---

6. 一般情况解法：树分治

对于树上任意路径问题，点分治是常用方法。

核心思想：
考虑当前分治中心 $rt$，对于 $rt$ 子树中的节点 $u$，它的路径可以分为两段：$u \to rt$ 和 $rt \to 1$。
如果我们在 $rt$ 处购票，则可以从 $rt$ 跳到某个祖先 $a$，这样 $u$ 的花费为 $dp_a + (d_u - d_a) \cdot p_u + q_u$，其中 $d_u - d_a \le l_u$。

---

分治步骤：

1. 找重心 $rt$。
2. 递归处理 $rt$ 的各个子树（不经过 $rt$ 的路径）。
3. 处理经过 $rt$ 的路径：
   • 收集 $rt$ 子树中所有节点 $u$。
   • 对每个 $u$，计算它到 $rt$ 的距离 $dis(u,rt) = d_u - d_{rt}$。
   • 对于 $rt$ 到根 $1$ 的祖先链，按 $d$ 从小到大加入凸壳（因为 $d$ 向根递减，但加入顺序反过来）。
   • 对每个 $u$，找到最小的 $d_a$ 满足 $d_a \ge d_u - l_u$（即最近的可跳祖先），在凸壳中查询斜率 $p_u$ 的最小截距，来更新 $dp_u$。
4. 继续递归 $rt$ 的子树。

---

关键细节：

• 凸壳按 $x = d_a$ 排序（递增），但祖先链上 $d$ 递减，所以要从根向 $rt$ 加入凸壳。
• 查询时，需要在凸壳中二分找到斜率 $p_u$ 的最优点。
• 由于 $l_u$ 限制，可能只需凸壳的一段，因此还需二分左边界。

---

7. 复杂度分析

每次分治，凸壳构建 $O(m)$（$m$ 为当前层点数），查询 $O(m \log m)$，总复杂度 $O(n \log^2 n)$。

如果用可持久化凸壳（主席树）可以做到 $O(n \log n)$，但实现复杂。

---

8. 总结步骤

1. DFS 预处理 $d_u$。
2. 初始化 $dp[1]=0$。
3. 对整树进行点分治：
   • 找重心。
   • 递归处理子树。
   • 构建祖先链凸壳。
   • 用祖先凸壳更新子树节点 DP 值。
4. 输出 $dp[2..n]$。

---

9. 注意事项

• 距离和费用可能很大，用 long long 存储。
• 二分斜率比较时注意避免浮点数误差，用交叉乘法比较。
• 凸壳维护时注意弹栈条件。
• 树分治中注意标记已访问的重心，避免重复。

---

这种“DP + 斜率优化 + 树分治”的组合，是解决树上路径限制优化问题的经典模式。