问题概述

给定一棵包含 $N$ 个节点的树，每条边有正权值。现有 $Q$ 个查询，每个查询给出两个节点集合 $X$（大小为 $S$）和 $Y$（大小为 $T$），要求计算： $\min_{x \in X, y \in Y} \text{dist}(x, y)$ 其中 $\text{dist}(x, y)$ 表示树上两点间的距离。

数据范围：

• $N \leq 5 \times 10^5$
• $Q \leq 10^5$
• $\sum S_i + \sum T_i \leq 2 \times 10^6$
• 边权 $\leq 10^9$

---

问题分析

朴素方法不可行

最直接的思路是对于每个查询，枚举 $X$ 和 $Y$ 中的所有点对，用 $O(1)$ 时间计算 LCA 距离。复杂度为 $O(\sum S_i T_i)$，最坏情况下可能达到 $O(N^2)$，无法接受。

关键观察

1. 查询点集总规模有限：虽然单次查询可能涉及很多点，但所有查询的总点数 $\sum (S_i + T_i) \leq 2 \times 10^6$，这提示我们可以设计复杂度与总点数相关的算法。
2. 树结构固定：可以预处理树的信息（深度、LCA 等）。
3. 需要快速处理集合间最近点对：这是典型的树上最近点对查询问题。

---

核心算法：点分治

算法思想

点分治通过递归地选取树的重心，将问题分解为经过重心的路径问题和子树内的子问题。

对于每个重心 $c$，记 $d_c(u)$ 为从 $c$ 到 $u$ 的距离。对于任意两点 $x$ 和 $y$，如果它们在 $c$ 的不同子树中，那么： $\text{dist}(x, y) = d_c(x) + d_c(y)$ 因为重心 $c$ 在 $x$ 到 $y$ 的路径上。

预处理阶段（Init 函数）

1. 构建树结构：存储邻接表，边权为 64 位整数。
2. 计算深度：从任意根节点开始 DFS，计算每个节点到根的距离。
3. 预处理 LCA：使用倍增法或欧拉序+RMQ 实现 $O(1)$ 的 LCA 查询。
4. 构建点分治树：
   • 找到整棵树的重心作为第一层重心
   • 删除重心后递归处理各连通块
   • 记录每个节点在点分治树上的祖先链

查询处理（Query 函数）

对于查询 $(X, Y)$，我们需要计算两集合间的最小距离。

主要思路：在点分治树上，从 $X \cup Y$ 中的节点向上遍历到根。对于每个重心 $c$，我们维护：

• $f_c$：集合 $X$ 中节点到 $c$ 的最小距离
• $g_c$：集合 $Y$ 中节点到 $c$ 的最小距离

那么经过 $c$ 的最短路径长度候选值为 $f_c + g_c$。

具体步骤：

1. 对 $X$ 中每个节点 $x$，沿点分治树向上遍历：
   • 对于每个祖先重心 $c$，更新 $f_c = \min(f_c, \text{dist}(x, c))$
2. 对 $Y$ 中每个节点 $y$ 同样处理，更新 $g_c$
3. 答案初始化为极大值
4. 对于每个重心 $c$，如果 $f_c$ 和 $g_c$ 都被更新过，则： $\text{ans} = \min(\text{ans}, f_c + g_c)$
5. 返回 $\text{ans}$

---

算法正确性证明

定理：对于任意两点 $x \in X, y \in Y$，设它们在点分治树上的最近公共重心为 $c$，则：

1. $c$ 在 $x$ 到 $y$ 的路径上
2. $\text{dist}(x, y) = \text{dist}(x, c) + \text{dist}(c, y)$
3. 在我们的算法中，$f_c \leq \text{dist}(x, c)$，$g_c \leq \text{dist}(c, y)$
4. 因此 $f_c + g_c \leq \text{dist}(x, y)$

由于我们取所有重心 $c$ 的 $f_c + g_c$ 的最小值，且至少有一个重心 $c$ 是 $x$ 和 $y$ 在点分治树上的 LCA，所以算法一定能找到 $\min_{x,y} \text{dist}(x, y)$。

---

复杂度分析

时间复杂度

1. 预处理：
   • 构建点分治树：$O(N \log N)$
   • 预处理 LCA：$O(N \log N)$
2. 单次查询：
   • 对于 $X$ 中每个点：沿点分治树向上，最多 $O(\log N)$ 个祖先
   • 对于 $Y$ 中每个点：同样 $O(\log N)$
   • 总复杂度：$O((S+T) \log N)$
3. 总查询复杂度：$O(\sum (S_i + T_i) \log N) \approx O(2 \times 10^6 \times 20) = O(4 \times 10^7)$，可接受。

空间复杂度

• 存储树：$O(N)$
• 点分治树：$O(N)$
• 查询临时数组：$O(N)$

---

实现细节

数据结构设计

struct Node {
    vector<pair<int, long long>> edges;  // 邻接表：(邻居, 边权)
    bool removed;  // 点分治中是否已删除
    int size, max_subtree;  // 子树大小，最大子树大小
    vector<int> centroids;  // 在点分治树上的祖先链
    vector<long long> dist_to_centroid;  // 到每个祖先重心的距离
};

点分治构建步骤

1. 计算子树大小：DFS 计算每个节点的子树大小
2. 找重心：找到满足 max_subtree ≤ total_size/2 的节点
3. 标记重心：将重心标记为已删除
4. 递归处理：对每个连通块重复上述过程
5. 记录信息：对于每个节点，记录其到所有祖先重心的距离

查询优化技巧

1. 批量处理：在查询开始时，为当前查询分配唯一 ID，避免每次查询都清空全局数组
2. 距离计算：利用 $\text{dist}(u, v) = \text{depth}[u] + \text{depth}[v] - 2 \times \text{depth}[\text{LCA}(u, v)]$
3. 初始化技巧：使用时间戳或查询 ID 来标记数组是否已更新，避免 $O(N)$ 的清空操作

---

特殊情况的处理

大权值处理

边权可达 $10^9$，$N$ 个节点的路径和可能超过 32 位整数范围，必须使用 64 位整数（long long）。

重复点处理

题目保证 $X$ 和 $Y$ 中的点互不相同，但 $X$ 内部或 $Y$ 内部可能有重复？实际上题目说 "彼此不同"，应该是指所有点都不同。

空集情况

题目保证 $S, T \geq 1$，不存在空集。

---

替代算法：虚树方法

除了点分治，还可以使用虚树（Virtual Tree） 方法：

1. 对于每个查询，构建 $X \cup Y$ 的虚树
2. 在虚树上进行树形 DP
3. 维护每个子树中到最近 $X$ 点和最近 $Y$ 点的距离
4. 答案即为某个节点处 $f_u + g_u$ 的最小值

虚树方法的复杂度：

• 构建虚树：$O(K \log K)$，$K = S+T$
• DP：$O(K)$
• 总复杂度：$O(\sum K_i \log K_i)$

与点分治相比，虚树方法在理论上更优，但实现相对复杂。

---

总结

本题是一个经典的树上最近点对查询问题，主要难点在于：

1. 大数据范围下的高效处理
2. 对多个查询的批量优化
3. 实现点分治或虚树算法

点分治解法的优势在于：

• 预处理后查询高效
• 实现相对直观
• 充分利用了 $\sum (S_i + T_i)$ 有限的特性

关键点：

• 利用点分治将路径分解为经过重心的路径
• 通过维护每个重心到两个集合的最小距离来快速查询
• 注意使用 64 位整数存储距离

该算法能够在 $N \leq 5 \times 10^5$，$Q \leq 10^5$ 的数据范围内高效运行，是解决此类问题的标准方法。