「蜀道难」题解

问题重述

我们有一棵树，需要给每个节点分配 $1$ 到 $n$ 的排列作为标号 $p(v)$。

约束条件

1. 距离图直径 ≤ 2：定义图 $G(T)$，其中两点 $u,v$ 之间有边当且仅当在树 $T$ 中 $u$ 到 $v$ 的路径上的标号是单调的（递增或递减）。要求 $G(T)$ 的直径 ≤ 2（任意两点间最短路 ≤ 2）。
2. 目标：最小化树的权值 $W(T) = \sum_{(u,v)\in E} |p(u)-p(v)|$。
3. 动态操作：初始给定一棵树，随后进行 $q$ 次操作，每次添加一个叶子节点，每次操作后都要输出当前的最小权值。

约束条件分析

距离图直径 ≤ 2 的含义

在 $G(T)$ 中，两点之间有边当且仅当它们在树上的路径标号单调。

关键观察：

• 如果两个节点 $u,v$ 在 $G(T)$ 中没有直接边，那么它们在树上的路径标号一定不是单调的（即先增后减或先减后增）。
• 直径 ≤ 2 意味着：对于任意两个节点 $u,v$，要么它们直接有边（路径单调），要么存在一个节点 $w$，使得 $u,w$ 和 $w,v$ 都有边（即 $u→w$ 和 $w→v$ 的路径都是单调的）。

这等价于：不存在三个节点 $a,b,c$，使得 $b$ 在 $a,c$ 的路径上，且 $p(a) < p(b) > p(c)$ 或 $p(a) > p(b) < p(c)$（即没有"山峰"或"山谷"形状）。

换句话说：树的标号必须是"单峰"的——存在一条路径（可能退化为点），使得从该路径向外，标号单调递减。

更形式化的表述

存在一个中心（可能是一条路径或一个点），满足：

1. 从中心向外，标号严格递减
2. 中心上的点，标号可以任意排列（但为了最小化权值，会有特殊安排）

问题转化

我们需要找到一种标号排列，使得：

1. 满足单峰性质（存在中心，向外递减）
2. 最小化 $\sum |p(u)-p(v)|$

这等价于：将树分解为一个中心（中心路径）和若干层（根据到中心的距离分层），然后给每层分配连续的标号区间。

中心的选择

设中心为一条路径 $C$（可能退化为点）。对于任意节点 $u$，设 $d(u)$ 为 $u$ 到 $C$ 的距离（在树上的边数）。

标号规则：

• 所有距离为 $d$ 的节点获得标号在某个区间 $[L_d, R_d]$
• 距离越大，标号区间越小（更小的数字）
• 即：$R_{d} < L_{d-1}$（外层标号小于内层标号）

这样，从中心向外走，标号严格递减，满足单调性条件。

权值计算

对于一条边 $(u,v)$：

• 如果 $u,v$ 在同一层，则 $|p(u)-p(v)|$ 较小
• 如果 $u,v$ 在相邻层，则 $|p(u)-p(v)|$ ≈ 层间标号差

目标：安排每层内部的标号顺序，以及层间标号区间的分配，最小化总权值。

算法框架

固定中心的情况

假设我们已经确定了中心路径 $C$。设 $L_d$ 为距离为 $d$ 的节点数。

层间贡献：

• 连接第 $d$ 层和第 $d+1$ 层的边：每条边的贡献至少为层间标号差
• 为了最小化，我们应让相邻层的标号区间尽可能接近

层内贡献：

• 第 $d$ 层内部的边（如果存在）：需要安排该层节点的标号顺序，最小化该层内部的 $\sum |p(u)-p(v)|$
• 这等价于：给定一个连通图（该层在树中的诱导子图），给节点分配连续标号，最小化边权和
• 对于树来说，最优安排是进行DFS序或BFS序，但需要具体分析

动态规划

我们可以设计一个树形DP：

状态：$dp[u]$ 表示以 $u$ 为根的子树，当 $u$ 是中心的一部分时，子树的最小权值。

但中心是一条路径，所以我们需要考虑路径的端点。

更进一步的观察

通过分析样例和性质，我们可以发现：

最优结构：存在一个节点 $r$（根），使得标号满足：

• 以 $r$ 为根，每个节点的标号小于其父节点的标号
• 同深度的节点标号连续

这样，从根向下标号递减，自然满足单调性条件。

证明思路：

1. 由于直径 ≤ 2 的限制，树必须有一个"中心"，从中心向外标号递减
2. 如果中心是一个点，那么树是以该点为根的"内向树"（所有边指向中心）
3. 如果中心是一条路径，那么可以转化为以路径中某点为根

转化到以某个点为根

设我们选择节点 $r$ 作为"最大标号"的节点（即 $p(r)=n$），然后标号沿着树递减。

这样，对于任意路径：

• 如果路径经过 $r$，则标号先增到 $r$ 再减，是单峰的
• 如果路径不经过 $r$，设最近公共祖先为 $lca$，则从 $lca$ 向两端都递减

这满足直径 ≤ 2 的条件吗？需要验证。

实际上，更精确的结构是：树必须是一个"毛毛虫"（caterpillar）——去掉所有叶子后得到一条路径（中心路径），所有叶子直接连在中心路径上。

验证：如果树不是毛毛虫，那么存在一个节点有两个非叶子邻居，这可能导致直径 > 2。

算法设计

基于以上分析，最优结构是：

1. 树是一个毛毛虫（中心路径 + 直接连接的叶子）
2. 标号沿着中心路径单调（递增或递减），叶子标号小于其连接的路径节点

最小权值计算

设中心路径长度为 $m$（节点数），路径节点标号为 $a_1, a_2, ..., a_m$，满足 $a_1 < a_2 < ... < a_m$ 或相反。

对于路径上的边 $(a_i, a_{i+1})$，贡献为 $|a_i - a_{i+1}|$

对于叶子 $l$ 连接到路径节点 $a_i$，贡献为 $|p(l) - a_i|$

优化目标：

1. 安排路径节点的标号（一个排列中的 $m$ 个位置）
2. 安排叶子的标号（剩下的 $n-m$ 个位置）
3. 最小化总权值

贪心策略

观察：为了最小化 $\sum |p(u)-p(v)|$，我们应该：

• 路径节点的标号尽量连续
• 叶子的标号尽量靠近其连接的路径节点

最优方案：

1. 将最大的 $m$ 个标号分配给中心路径节点
2. 将这些标号按路径顺序排列为连续区间
3. 将剩下的标号分配给叶子，每个叶子标号小于其连接的路径节点

这样，路径边贡献为 $m-1$（如果使用 $n, n-1, ..., n-m+1$） 叶子边贡献：每个叶子标号比路径节点小，具体值取决于如何分配。

精确计算

设中心路径节点获得标号 $n, n-1, ..., n-m+1$，按路径顺序排列。 对于连接到标号为 $x$ 的路径节点的叶子，有 $k$ 个叶子，那么这些叶子应获得标号 $x-1, x-2, ..., x-k$。

总权值 = 路径边权和 + 叶子边权和

• 路径边权和 = $(m-1)$（因为相邻标号差为1）
• 叶子边权和 = $\sum_{i=1}^m \sum_{j=1}^{k_i} j = \sum_{i=1}^m \frac{k_i(k_i+1)}{2}$

其中 $k_i$ 是连接到第 $i$ 个路径节点的叶子数（不包括路径上的邻居）。

动态维护

当添加一个叶子时：

1. 如果连接到路径节点：$k_i$ 增加，权值增加 $(k_i+1)$（因为 $\frac{(k+1)(k+2)}{2} - \frac{k(k+1)}{2} = k+1$）
2. 如果连接到叶子：可能需要改变中心路径的选择

关键问题：如何选择中心路径？对于一棵树，中心路径应该是直径吗？

最终算法

步骤1：找到中心路径

中心路径应该是树的直径吗？不一定，但可以证明：

• 在最优解中，中心路径是树的最长路径（直径）
• 因为更长的路径允许分配更大的标号差，但分析表明，路径长度增加会增加路径边权和，但可能减少叶子边权和

实际上，我们需要选择一条路径 $P$，最小化：

$$W(P) = (|P|-1) + \sum_{v \notin P} dist(v, P)$$

其中 $dist(v, P)$ 是 $v$ 到 $P$ 的距离（边数）。

这是因为：

• 路径边权和 = $|P|-1$
• 对于每个叶子（或非路径节点），如果距离路径为 $d$，那么它需要 $d$ 个递减的标号，贡献约为 $\frac{d(d+1)}{2}$，但精确值需要更仔细计算

简化版本

对于每个节点 $v \notin P$，设它连接到路径上的节点 $u$，距离为 $d$。那么从 $v$ 到 $u$ 的路径上需要分配 $d+1$ 个连续递减的标号。

实际上，更精确的公式是： 设路径 $P$ 上的节点标号为 $a_1, ..., a_m$（递减），对于不在 $P$ 上的节点 $v$，设它连接到 $a_i$ 通过长度为 $d$ 的路径，那么这条路径上的节点标号应该是 $a_i-1, a_i-2, ..., a_i-d$。

因此，总权值可以计算为。

动态维护算法

由于 $n+q \leq 10^5$，我们需要 $O((n+q)\log n)$ 或类似的算法。

算法概要：

1. 初始时，找到树的一条直径作为中心路径
2. 计算初始权值
3. 对于每次添加叶子：
   • 如果叶子连接到路径节点：直接更新权值
   • 如果叶子连接到非路径节点：可能需要重新选择中心路径
   • 但重新计算直径的代价太高

启发式方法

注意到树的直径可以在添加叶子时高效维护：

• 当添加叶子 $v$ 到节点 $u$ 时，新的直径端点可能是原来的直径端点，或者是 $v$ 到某个原直径端点的路径
• 可以用两次BFS/DFS找到直径

但每次 $O(n)$ 的 BFS 对于 $10^5$ 操作来说太慢。

最终解决方案

实际上，通过深入分析，可以发现：

定理：最优中心路径是树的直径。

证明思路：

1. 任何其他路径都可以通过扩展来减少叶子到路径的总距离
2. 直径最大化路径长度，但最小化平均距离

因此，算法为：

1. 维护树的直径
2. 计算以直径为中心路径的权值

权值计算： 设直径长度为 $L$（边数），直径节点数为 $L+1$。 对于每个节点 $v$，设 $d(v)$ 为 $v$ 到直径的距离（边数）。

总权值 = $(L) + \sum_{v} \frac{d(v)(d(v)+1)}{2}$

因为：

• 直径边：$L$ 条边，每条边权值为1（如果我们用最大标号）
• 非直径节点：距离为 $d$ 的节点贡献 $\frac{d(d+1)}{2}$

动态维护： 当添加叶子 $v$ 到节点 $u$ 时：

1. 更新直径（如果需要）
2. 计算 $d(v) = d(u) + 1$
3. 权值增加 $\frac{d(v)(d(v)+1)}{2} - \frac{d(u)(d(u)+1)}{2}$（如果 $u$ 是直径节点，则 $d(u)=0$）

直径维护

维护树的直径：

• 存储当前直径端点 $a, b$
• 当添加叶子 $v$ 到 $u$ 时：
  • 计算 $dist(a, v)$ 和 $dist(b, v)$
  • 如果 $dist(a, v) > dist(a, b)$，则新直径为 $(a, v)$
  • 如果 $dist(b, v) > dist(a, b)$，则新直径为 $(b, v)$
  • 否则直径不变

需要高效计算树上距离：使用 LCA（最近公共祖先），预处理 $O(n\log n)$，查询 $O(\log n)$。

复杂度分析

• 预处理：$O(n\log n)$ 建立LCA
• 每次添加叶子：$O(\log n)$ 计算距离，更新权值
• 总复杂度：$O((n+q)\log n)$

总结

本题的核心是将复杂的约束条件转化为树的结构性质：

1. 直径 ≤ 2 的条件强制树必须是"毛毛虫"状
2. 最优标号方案是：选择直径作为中心路径，分配最大标号，向外递减
3. 权值可以公式化计算
4. 动态维护直径和权值