题目理解

我们有一个 $N$ 个节点的树，每个节点的度数不超过 $18$。我们不知道树的结构，但可以通过以下方式查询：

Query(u, v, w)：返回树中使得 $dist(u,x) + dist(v,x) + dist(w,x)$ 最小的节点 $x$（即三点的重心）。

我们需要通过不超过 $10^5$ 次查询，还原整棵树的结构，并用 Bridge(u, v) 报告所有边。

---

关键性质分析

1. 三点聚会的性质

对于树上的三点 $u,v,w$，它们的聚会点 $m = Query(u,v,w)$ 是三点的重心，具有以下性质：

$m$ 在 $u,v,w$ 三点的斯坦纳树上

$m$ 是树中唯一满足到三点距离和最小的点

如果某点在三点两两之间的简单路径的交点上，那么它可能是重心

2. 重心的等价描述

设 $m = Query(u,v,w)$，那么：

$m$ 在 $u$ 到 $v$ 的路径上，或在 $u$ 到 $w$ 的路径上，或在 $v$ 到 $w$ 的路径上

实际上，$m$ 是三点的中间点，即到三点距离方差最小的点

3. 重要引理

引理 1：对于任意两点 $u,v$ 和第三点 $w$，如果 $Query(u,v,w) = w$，那么 $w$ 在 $u$ 到 $v$ 的路径上。

证明：如果 $w$ 不在 $u$ 到 $v$ 的路径上，那么重心会在 $u$-$v$ 路径上的某点，而不是 $w$。

引理 2：对于任意两点 $u,v$，存在一个点 $w$ 使得 $Query(u,v,w) = w$ 当且仅当 $w$ 在 $u$ 到 $v$ 的路径上。

4. 路径检测与重构

基于以上引理，我们可以设计算法：

路径检测：要判断 $w$ 是否在 $u$ 到 $v$ 的路径上，只需检查 $Query(u,v,w) == w$。

找路径上所有点：对于已知在路径上的两点 $u,v$，要找到它们之间的所有点，可以遍历所有其他点 $x$，检查是否 $Query(u,v,x) = x$。

---

算法设计

思路：增量构建

我们从单个节点开始，逐步将新节点加入到已知的连通分量中。

初始状态：已知部分节点和它们之间的连接关系

选择新节点：每次选择一个还未加入的节点 $x$

寻找连接点：在已知的连通分量中找到 $x$ 应该连接到的节点

关键问题：如何找到 $x$ 的连接点？

设当前已知的连通分量为 $T$，我们要找 $x$ 在 $T$ 中连接到的节点 $p$。

观察：$p$ 是 $T$ 中离 $x$ 最近的节点。对于 $T$ 中任意两点 $u,v$，如果 $p$ 在 $u$ 到 $v$ 的路径上，那么 $Query(u,v,x)$ 会返回 $p$。

具体算法步骤

随机选择一个节点 $r$ 作为根，构建以 $r$ 为中心的生成树

维护已知的树结构 $T$，初始 $T = {r}$

对于每个未加入的节点 $x$：

在 $T$ 中找到离 $x$ 最近的节点 $p$

将 $x$ 连接到 $p$

如何找最近节点 $p$？ 使用二分查找在已知树上定位：

从 $T$ 中随机选择一些节点作为候选

找到候选节点中离 $x$ 最近的（通过 Query 判断）

在路径上进一步精确定位

最近节点判定：对于 $T$ 中节点 $u,v$，如果 $Query(u,v,x)$ 返回 $u$，则 $x$ 离 $u$ 更近；如果返回 $v$，则离 $v$ 更近；如果返回其他点 $w$，则 $w$ 离 $x$ 更近。

---

复杂度分析

每个节点加入时，需要 $O(\log N)$ 次 Query 来定位连接点

总 Query 次数：$O(N \log N)$，对于 $N \leq 2000$，远小于 $10^5$

每个节点度数不超过 $18$ 保证了树的平衡性，使得二分查找有效

---

数学公式与证明

距离和最小化公式

设 $d(u,v)$ 表示树上两点间距离，三点 $u,v,w$ 的聚会点 $m$ 满足：

$$m = \arg\min_{x \in V} \left[ d(u,x) + d(v,x) + d(w,x) \right] $$

路径上的重心性质

对于在路径上的三点 $u \to p \to v$，有： Query(u,v,p)=p⟺p 在 u到 v的路径上 Query(u,v,p)=p⟺p 在 u 到 v 的路径上

最近节点判定公式

对于节点 $x$ 和树 $T$ 中两点 $u,v$，设 $m = Query(u,v,x)$：

如果 $m = u$，则 $d(x,u) < d(x,v)$

如果 $m = v$，则 $d(x,v) < d(x,u)$

如果 $m = w \neq u,v$，则 $d(x,w) < \min(d(x,u), d(x,v))$

---

优化技巧

1.随机化：随机选择查询顺序可以减少最坏情况

2.度数利用：已知最大度数为 $18$，可以设计更精细的定位策略

3.批量查询：对多个候选点可以设计更高效的比较方法