FRT 随机树嵌入 | Codeboy's Blog

一棵树上的两点只有一条通路，距离和分治都容易处理；一般度量未必有这样的结构。FRT 的做法是抽取一棵带额外内部节点的树，把原来的点保留为叶子。树中所有原点对的距离都不变小，个别距离可能变得很大；但对任何在抽树之前就固定的点对，树距离的平均增长只有对数级。构造靠逐层划分，关键证明却不能把每层的误差简单相加成“层数乘对数”。

形式陈述

输入与概率保证

给定 $n$ 点有限度量 $(X,d)$ 。先处理 $n\ge2$ ，记最小正距离为 $m$ 、直径为 $D$ 、宽高比为 $\Phi=D/m\ge1$ 。输出是一棵带非负边长的有根树，原点各对应一片不同的叶子，内部节点可以是额外的层级集合。树路径距离记为 $d_T$ 。

本页给出的具体标号版本满足

\forall T\text{ 可能输出},\ \forall u,v\in X, \quad d_T(u,v)\ge d(u,v),

以及

\forall u,v\in X,\qquad \mathbb E_T d_T(u,v)\le8H_n d(u,v), \quad H_n=\sum_{j=1}^n\frac1j\le1+\ln n.

前者是每次执行同时成立的不收缩保证；后者先固定点对，再对树取期望。它没有给每棵输出树一个同时控制所有点对的 $8H_n$ 上界。Fakcharoenphol、Rao 与 Talwar 证明了这种 $O(\log n)$ 概率嵌入。[1, Theorem1] 下面的常数 $8$ 对应本页明确指定的节点标签和边权，需由后面的证明读取。

$n=0$ 返回空结构， $n=1$ 返回单个标号零的叶子；两种情形的所有距离保证直接成立，不计算最小正距离或 $\log\Phi$ 。若输入图不连通，跨分量的无穷距离不属于本页有限度量合同。

同一份随机带贯穿各层

取

\ell=\lfloor\log_2m\rfloor,\qquad L=\lceil\log_2D\rceil+2,\qquad \Delta_i=2^i\quad(\ell\le i\le L).

从大到小处理这些层。独立选择均匀排列 $\pi$ 和均匀 $\beta\in[1,2)$ ，所有层共享它们；第 $i$ 层半径为

R_i=\beta\Delta_i/4.

因此单看任一层，半径正好均匀分布在 $[\Delta_i/4,\Delta_i/2)$ ，符合CKR 单尺度划分的合同。各层并不独立。

在每层，令 $Q_i$ 是全空间按同一中心顺序、半径 $R_i$ 得到的 CKR 划分。然后令 $P_i$ 为 $Q_i$ 与上一层 $P_{i+1}$ 的共同细化：只有上一层同块且本层主人相同的点才能继续同块。顶层 $P_L=Q_L=\{X\}$ ，因为 $R_L\ge D$ ；底层 $Q_\ell$ 全是单点，因为 $R_\ell<2^{\ell-1}\le m/2$ 。

实现时可给每点记录键 (上一层块ID, 本层主人ID)，相同键归为一个新块。即使某个中心在当前父块之外，也照常作为全局中心参与；原论文的层级构造明确允许这种块外中心。[1, §2.3]

从嵌套块变成真实带权树

每个层级块建立一个节点，父节点是上一层包含它的块。第 $i$ 层的非底层节点标号 $\Gamma=\Delta_i$ ；底层单点节点标号零，作为原点叶子。对每条父子边规定

\operatorname{length}(p,c)=\frac{\Gamma(p)-\Gamma(c)}2.

标签向下递减，所以边长非负。两叶 $u,v$ 的路径先到最近公共祖先 $w$ ，再向下到另一叶；每半边的标签差望远镜相消，得到

d_T(u,v)=\Gamma(w).

这还给出超度量不等式 $d_T(u,v)\le\max\{d_T(u,z),d_T(z,v)\}$ ：若 $u,z$ 在某层同块、 $z,v$ 也在该层同块，则 $u,v$ 必然同块。树距离因此比一般度量多了一层嵌套结构。

直觉

粗尺度先决定大组，细尺度再把每组内部拆开。近点若直到很细的层才分开，就共享一个低标号祖先，树距离较小；若很早分开，公共祖先标号高，树距离就大。随机化的目的不是排除后一种情况，而是让一个事先指定的近点对很少遇上它。

每个中心都有一段可能切开该点对的危险半径区间。这段区间的长度至多是两点原距离。虽然算法有很多尺度，半径窗口从一个二倍区间移到下一个，彼此不重叠；同一段危险区间跨所有尺度累计仍只有原来那么长。再按中心的竞争次序支付 $1,1/2,1/3,\ldots$ ，最终才得到调和因子，而不是额外支付整个宽高比。

五点在各尺度共同细化为树；父子边长由标签差的一半给出，叶距离读取公共祖先标签 — 层级块、节点标签与叶距离

不收缩先于概率分析

任一 $P_i$ 的块都是某个 $Q_i$ 块的子集，因此原度量直径至多 $\Delta_i$ 。若两片不同叶的 LCA 是第 $i$ 层节点，它们都属于该块，所以

d(u,v)\le\Delta_i=\Gamma(\operatorname{LCA}(u,v))=d_T(u,v).

这是对每一份随机带的确定性证明。它无需任何期望估计，也不要求原度量能由输入图中的某棵生成树表示。新增内部节点和新边长是输出的一部分。

跨尺度一次性支付危险区间

固定不同的 $u,v$ ，记 $\delta=d(u,v)$ 。对每个可能中心 $z$ ，设

a_z=\min\{d(z,u),d(z,v)\},\qquad b_z=\max\{d(z,u),d(z,v)\}.

按 $a_z$ 非降排序得到 $z_1,\ldots,z_n$ ，平局固定处理。反三角不等式给 $b_{z_j}-a_{z_j}\le\delta$ 。

记 $E_i$ 为原始单尺度划分 $Q_i$ 拆开 $u,v$ 的事件。若半径 $R_i$ 落在 $[a_{z_j},b_{z_j})$ ，中心 $z_j$ 只覆盖其中一端；它还必须在所有能够覆盖至少一端的中心中最早出现，才真正造成分离。固定半径后，前 $j$ 个中心都能触及这对点，故这项概率至多 $1/j$ 。于是

\Pr(E_i)\le\sum_{j=1}^n\frac1j\frac4{\Delta_i} \left|[a_{z_j},b_{z_j})\cap[\Delta_i/4,\Delta_i/2)\right|.

这里不能直接把区间交长度全部换成 $\delta$ 后再跨层求和，否则会丢掉要利用的结构。

设 $h$ 是发生 $E_i$ 的最大层号。顶层不分离、底层必分离，所以 $h$ 存在且 $h<L$ 。共同细化使两点在 $P_{h+1}$ 仍同块、在 $P_h$ 首次分开，因此 LCA 恰在第 $h+1$ 层，

d_T(u,v)=2\Delta_h\le\sum_{i=\ell}^L2\Delta_i\mathbf1_{E_i}.

取期望并交换有限求和，得到

\mathbb E d_T(u,v) \le8\sum_{j=1}^n\frac1j \sum_{i=\ell}^L \left|[a_{z_j},b_{z_j})\cap[2^{i-2},2^{i-1})\right|.

内层窗口两两不交，所以其总交长至多 $b_{z_j}-a_{z_j}\le\delta$ 。代入便有 $\mathbb E d_T(u,v)\le8H_n\delta$ 。这是消去宽高比的实际步骤。线性性没有要求不同层独立；共享排列和 $\beta$ 完全符合证明。[2, §15.3]

例子与边界

一份能逐边求和的树

令 $X=\{0,1,2,3,4\}$ 、 $d(u,v)=|u-v|$ ，取 $\pi=(2,0,4,1,3)$ 、 $\beta=3/2$ 。此时 $m=1,D=4$ ，层号为 $4,3,2,1,0$ 。

层号 $i$	半径 $R_i$	层级块 $P_i$	节点标签
$4$	$6$	$\{0,1,2,3,4\}$	$16$
$3$	$3$	$\{0,1,2,3,4\}$	$8$
$2$	$3/2$	$\{0\}$ ， $\{1,2,3\}$ ， $\{4\}$	$4$
$1$	$3/4$	五个单点块	$2$
$0$	$3/8$	五个单点叶	$0$

$1,3$ 的 LCA 是标签 $4$ 的块，各自从叶向上走两条长度 $1$ 的边，故 $d_T(1,3)=4$ 。 $0,1$ 的 LCA 标签为 $8$ ，各自到该祖先的路径长 $1+1+2=4$ ，故 $d_T(0,1)=8$ ，而原距离只有 $1$ 。根标签 $16$ 不会出现在不同叶对的距离中，因为根只有一个孩子；保留它只是为了完整展示顶层构造。

共同细化不能省

只把排列改成 $(0,4,2,1,3)$ ，仍取 $\beta=3/2$ 。半径 $3$ 时，原始划分是 $\{0,1,2,3\}$ 与 $\{4\}$ ；半径 $3/2$ 时，原始划分变为 $\{0,1\}$ 、 $\{3,4\}$ 、 $\{2\}$ 。后者的 $\{3,4\}$ 跨过了前一层边界，不能直接当作某个父块的孩子。

正确的细化结果是 $\{0,1\}$ 、 $\{2\}$ 、 $\{3\}$ 、 $\{4\}$ 。主人相同只是一个条件，还要保留父块身份。若遗漏这个身份，输出可能不是层级树，LCA 证明的前提随之消失。

罕见的大伸长确实会发生

把第五点移到 $1024$ ，得到 $X=\{0,1,2,3,1024\}$ ，身份仍是 $0,1,2,3,4$ 。取中心顺序 $(4,0,1,2,3)$ 、 $\beta=2047/1024$ 。在第 $11$ 层，半径为 $2047/2=1023.5$ ；最先处理的远端点覆盖位置 $1$ ，却覆盖不到位置 $0$ 。这对相距 $1$ 的点首次在该层分离，其树距离为 $4096$ 。

而 $8H_5=274/15$ ，远小于 $4096$ 。这份合法输出直接否定“每棵树所有点对都至多伸长 $8H_5$ ”。按全部排列和真实半径区间精确积分，身份 $0,1$ 的期望树距离为 $3967/480$ ，仍在定理界内。坏随机带有正概率，并非只能在概率零的边界上出现。

推论与应用

固定费用可以传到树上

给定与随机树无关的非负权重 $w_{uv}$ ，线性性给出

\sum_{u<v}w_{uv}d(u,v) \le\mathbb E\sum_{u<v}w_{uv}d_T(u,v) \le8H_n\sum_{u<v}w_{uv}d(u,v).

五点主例只给四对相邻点权重一，原总距离为 $4$ ，精确平均树费用为 $442/15$ 。固定路径的移动费用也是这种和；不需要不同边的伸长相互独立。

把这种工具用于度量任务系统等优化模型，还要检查可行解怎样在树与原空间之间转换。可以先固定原问题的一条比较路径，再对它的树费用取期望；不能先观察随机树、再挑一条最坏短边，并声称同一个固定路径界仍然适用。具体在线竞争比还取决于树上算法和对手信息，嵌入定理本身没有给出它们。

树大小与构造时间不是同一个量

朴素实现处理 $q=L-\ell+1=O(1+\log\Phi)$ 层，每层做 $O(n^2)$ 次距离访问和 $O(n)$ 个归组键，故构造为 $O(n^2q)$ 次基本操作。若归组用哈希表，键操作按通常期望常数时间记；改用排序则每层另有 $O(n\log n)$ ，仍被二次项吸收。附件还直接计算全部叶对的 LCA 标签，需 $O(n^2q)$ ，输出距离矩阵占 $O(n^2)$ 。

保留每层所有块及点成员，证据占 $O(nq)$ 。压掉单孩子内部节点并把相邻边长相加，不改变任意叶对距离；再去掉根上方无分支链后，每个内部节点至少有两个孩子，因而至多 $n-1$ 个内部节点，紧凑树只有 $O(n)$ 个节点。附件为了可检查性保留未压缩层级，不能把紧凑树的空间界直接报给它。

原始距离矩阵本身另占 $O(n^2)$ ，一次距离 oracle 的费用另乘，全部三角检验仍为 $O(n^3)$ 。对于分子分母至多 $B$ 位的有理输入，尺度指数绝对值为 $O(B)$ ， $q=O(B)$ ；若给定的有理随机带 $\beta$ 另占 $B_\beta$ 位，基本半径比较可保守按 $O((B+B_\beta)^2)$ 位成本计算，标签本身仍只需 $O(B)$ 位。附件的精确期望枚举会把大量概率分数相加，其累积分母可能更长，不能给它套用单次树构造的位界。

概率分析已经消掉 $\log\Phi$ ，这份逐层实现的时间尚未消掉。原论文和后续工作有更精细的构造算法，[1, §2.3] 本页没有以一句“O(n²)”替代未实现的数据结构。

连续随机量也能在小例上精确核验

对有理距离表，执行只会在 $\beta=4d(u,v)/2^i$ 这样的阈值处改变。收集落在 $(1,2)$ 的全部阈值，连同端点切成区间；每个开区间取一个有理内点重放，权重就是区间长度。再枚举全部 $n!$ 个排列，每项权重乘 $1/n!$ 。边界点概率零，不影响积分；内点执行仍采用闭球规则。

五点主例只需把 $[1,2)$ 切为 $[1,3/2)$ 与 $[3/2,2)$ ，共重放 $240$ 份带权随机带。单元终点要求交完整的点对期望矩阵，而不是只报一个随机种子的平均值。这个阶乘级积分器是小实例核验工具；实际采样一棵树只运行一次构造。

参考资料

Jittat Fakcharoenphol、Satish Rao、Kunal Talwar，A Tight Bound on Approximating Arbitrary Metrics by Tree Metrics，STOC2003，pp.448–455，§§2.1–2.3 的层级、共享随机带与 Theorem1；§2.5 的固定权重视角。期刊版发表于 JCSS69(3)，2004，pp.485–497。原文边长约定与本页标签差约定不同。
Michael Dinitz，Approximation Algorithms，Lecture15，JHU，2024-03-12，§§15.1–15.3，pp.1–6：树叶接口、最先触及中心以及跨尺度区间长度记账。

形式陈述 ​

输入与概率保证 ​

同一份随机带贯穿各层 ​

从嵌套块变成真实带权树 ​

不收缩先于概率分析 ​

跨尺度一次性支付危险区间 ​

一份能逐边求和的树 ​

共同细化不能省 ​

罕见的大伸长确实会发生 ​

固定费用可以传到树上 ​

树大小与构造时间不是同一个量 ​

连续随机量也能在小例上精确核验 ​

反向链接