沿有限度量学习路线，先用 最远点优先理路最远点优先 k-centerFarthest-first traversal · Gonzalez k-center algorithm · Metric k-center · 最远点优先遍历每次选离现有中心最远的点，以覆盖半径和 k+1 个分离点共同证明离散度量 k-center 的二倍近似。控制最坏服务距离，再用 CKR理路CKR 随机球划分CKR partition · Calinescu–Karloff–Rabani partition · 随机球划分 · 随机低直径划分用随机半径和随机中心顺序划分有限度量，保持每块弱直径受限，并以调和求和控制近点或小球被拆开的概率。研究一个尺度的随机边界，最后把各层共同细化成 FRT 树理路FRT 随机树嵌入FRT tree embedding · Fakcharoenphol–Rao–Talwar embedding · Probabilistic tree embedding · 随机度量树嵌入将有限度量随机嵌入逐点对不收缩的层级树，以跨尺度区间记账证明每个固定点对的期望伸长为 O(log n)。。本终点不把三种输出混成“聚类效果”：中心预算、块直径与树伸长分别有自己的可检查规格。

下载标准库核验器 · 完整精确输出。执行 python algorithms-metric-cover-trees-check.py，JSON 写到标准输出。所有数学检查使用显式异常，python -O 不会把检查关掉。点身份从零开始，坐标只在本例用来生成距离表。

任务一：覆盖与最优下界同时交付 ​

输入坐标为 $(0,1,2,3,4)$，距离 $d(i,j)=|i-j|$，选 $k=2$ 个原点作中心，起点固定为身份 $0$。提交中心加入次序、每点主人、最近距离、最终半径以及三个分离见证。

第一轮距离为 $(0,1,2,3,4)$，最远点为 $4$；第二轮距离变为 $(0,1,2,1,0)$，结束选点。中心为 $\{0,4\}$，主人数组为 $(0,0,0,4,4)$，半径为 $2$。见证顺序为 $(0,4,2)$，两两距离分别为 $4,2,2$，因此最优半径至少为 $1$。

枚举十个中心对，最优半径为 $1$。程序按身份字典序选出 $\{0,3\}$，$\{1,3\}$ 也是最优。必须报告“半径 $2$、下界 $1$”，不能把证书中分离距离 $2$ 直接写成最优半径下界。核验器仅需中心、指派、半径和分离见证即可验证二倍近似；最近距离数组和轨迹另供执行审查。

主过程恰做 $nk=10$ 次距离查询。这个数字不包括矩阵入口验证、证书验证和中心组合穷举。将全部 $n$ 点都设为中心时，应得到零半径且没有第 $n+1$ 个见证；空输入只接受 $k=0$。

任务二：按随机带重放单尺度块 ​

取 $\mathrm{\Delta }=4$，中心处理顺序 $(2,0,4,1,3)$，用 $\beta =3/2$ 表示半径 $R=\beta \mathrm{\Delta }/4=3/2$。依次写出非空领取集：

1. 中心 $2$ 领取 $\{1,2,3\}$
2. 中心 $0$ 领取 $\{0\}$
3. 中心 $4$ 领取 $\{4\}$

主人数组为 $(0,2,2,2,4)$。两种“中心”不可混读：任务一从预算中挑了两站；本任务所有五点依次尝试领取，最后只有三个非空块。

恢复概率分布后，排列有 $120$ 种，$R$ 在 $[1,2)$ 均匀。对点对 $0,1$，候选中心 $\{0,1,2\}$ 中只有 $2$ 会只覆盖一端，所以分离概率为 $1/3$。对 $1,2$，四个候选中心中有两个只覆盖一端，概率为 $1/2$。对闭球 $B(2,1)=\{1,2,3\}$，只有中心 $2$ 最先触及它时才完整保留，故失败概率为 $4/5$。

这些是实际分布，不是把通用上界当成等式。这里 $H_5=137/60$，padding 的通用失败上界 $min\{1,8H_5/4\}$ 只给出 $1$，仍然正确但没有额外信息。

任务三：层级块、边权和全部叶距离 ​

继续用同一排列与 $\beta$。最小正距离 $m=1$、直径 $D=4$，所以层号从 $4$ 到 $0$。半径依次为 $6,3,3/2,3/4,3/8$，块依次为：全体、全体、$\{0\}$/$\{1,2,3\}$/$\{4\}$、五单点、五单点叶。

内部标签依次为 $16,8,4,2$，底层叶标零；边长取标签差的一半。原始证据树有 $15$ 个节点、$14$ 条边，父子层间边长依次为 $4,2,1,1$。主人相同的点还要来自同一个父块，不能只凭单尺度主人重新合并已经分开的点。

提交的叶距离矩阵应为

$$\left(\begin{array}{ccccc}0& 8& 8& 8& 8\\ 8& 0& 4& 4& 8\\ 8& 4& 0& 4& 8\\ 8& 4& 4& 0& 8\\ 8& 8& 8& 8& 0\end{array}\right).$$

至少逐边核算两项：$1$ 到 $3$ 的两段上行/下行路径各长 $2$，总和 $4$；$0$ 到 $1$ 的两段各长 $4$，总和 $8$。再检查全部点对 $d_T\ge d$。程序的构造与全距离输出共用这份层级；本次单尺度距离访问累计 $48$ 次，不包含输入验证与后续矩阵核验。

任务四：把连续半径真正积掉 ​

各层半径都由同一个 $\beta$ 缩放，不能逐层重新独立抽样。对本例，所有会改变层级的内部阈值只有 $\beta =3/2$。两个区间长度都是 $1/2$，每个排列分别在区间内取一点重放，总共 $120\times 2=240$ 份带权执行；概率质量之和必须恰为 $1$。

精确平均树距离为

$$\mathbb{E}{d}_T=\left(\begin{array}{ccccc}0& 116/15& 48/5& 56/5& 64/5\\ 116/15& 0& 7& 44/5& 56/5\\ 48/5& 7& 0& 7& 48/5\\ 56/5& 44/5& 7& 0& 116/15\\ 64/5& 56/5& 48/5& 116/15& 0\end{array}\right).$$

每项均在 $d(u,v)$ 与 $(274/15)d(u,v)$ 之间，因为 $8H_5=274/15$。仅给四对相邻点权重一，原总费用为 $4$，期望树费用为

$$116/15+7+7+116/15=442/15.$$

这些权重在抽树之前固定。若根据输出再挑伸长最大的点对，随机变量已经换成最大值，不能直接沿用逐固定点对期望。

区间积分器采用精确 Fraction，不用浮点网格。半径等于某个距离时的闭球边界也可单独重放，但这些单点在连续分布中的概率是零。枚举排列的成本为阶乘级，只用于小例的独立核验，不属于 FRT 单次构造的复杂度。

迁移一：宽高比增加而定理常数不变 ​

把坐标改为 $(0,1,2,3,1024)$，身份仍为 $0,1,2,3,4$。现在宽高比为 $1024$，朴素构造处理第 $12$ 层到第 $0$ 层，共 $13$ 层。精确积分需五个区间，内部阈值为

$$3/2,1021/512,511/256,1023/512,$$

共 $600$ 份带权执行。不能把它们等权平均，因为区间长度不同。

身份 $0,1$ 的原距离仍为 $1$，期望树距离为 $3967/480$。另一方面，排列 $(4,0,1,2,3)$ 配 $\beta =2047/1024$ 时，远端中心在半径 $1023.5$ 下只覆盖这对点中的位置 $1$，导致树距离 $4096$。请同时解释：为何这份输出不违反不收缩；为何它否定每棵树的统一小伸长；为何它仍与固定点对的期望界相容。

证明中的无宽高比来自每个中心的危险区间跨尺度只计一次；实现的 $13$ 层工作并没有凭证明消失。把运行时间也报成无尺度因子，需实现另一个更精细的构造。

迁移二：已有主人不等于失去中心资格 ​

取四点星图，中心身份 $1$，叶身份 $0,2,3$，三条边都长一。距离表为

$$\left(\begin{array}{cccc}0& 1& 2& 2\\ 1& 0& 1& 1\\ 2& 1& 0& 2\\ 2& 1& 2& 0\end{array}\right).$$

取 $\mathrm{\Delta }=8/3$、$\beta =3/2$，半径恰为 $1$，排列为 $(0,1,2,3)$。中心 $0$ 领取 $\{0,1\}$，已经有主人的中心 $1$ 再领取 $\{2,3\}$，主人数组为 $(0,0,1,1)$。

第二块的弱直径为 $2$，但诱导子图断开，内部没有从 $2$ 到 $3$ 的路径。这同时检验全局中心规则和强弱直径边界。若“跳过已领取的中心”，会错误输出两个额外单点块。

迁移三：原始各层未必构成树 ​

回到五个共线点，把排列改为 $(0,4,2,1,3)$，仍取 $\beta =3/2$。半径三的原始块是 $\{0,1,2,3\}$ 与 $\{4\}$，半径 $3/2$ 的原始块却含 $\{3,4\}$。共同细化必须把这个跨父块集合拆成 $\{3\}$ 与 $\{4\}$。

核对附件 crossing_raw_partitions 中的本层主人与父块身份。只保存本层主人会制造跨父节点的孩子；即便每一层单独看都是合法划分，合起来也未必是有根树。

最后核算接口与成本 ​

核验器入口明确拒绝十一种输入：非对称、零距离异点、平方差违反三角、非方阵、布尔距离、布尔 k、非空零 k、非正尺度、布尔排列身份、$\beta =2$ 和浮点随机量。实际拒绝与数学合同相符，不把 Python 中 True 与 1 相等当成合法身份。空集、单点、全部选为中心则实际运行正确出口。

在已承诺为度量、一次距离访问为单位成本的模型下，k-center 是 $O(nk)$，CKR 单尺度为 $O(n^2)$，本版逐层 FRT 连同全部叶对查询为 $O(n^{2}q)$，其中 $q=O(1+\log \mathrm{\Phi })$。稠密输入另占 $O(n^2)$，完整层级证据占 $O(nq)$，全叶距离输出再占 $O(n^2)$。验证所有三角不等式的 $O(n^3)$、最优中心穷举和阶乘随机带积分分别计账。

提交时应能回答三个不同的问题：哪些点确实被所选中心覆盖？一个固定小球以多大概率完整留下？一对固定原点在随机树中的距离平均增加多少？一份核验通过的结果必须让这三种量都能按原点身份重新计算。