# 一类四邻接网格图森林的匹配问题：按长分枝计费 **历史研究记录（2026-10-12 更新）。** 一般三次方上界现已由[独立证明](cubic-bound.zh.md)解决。下文保留各阶段的推导、余项和反例；“尚未解决”指当时状态或该局部方法，更强的辅助命题不自动随一般上界成立。 本篇分析现有候选列表算法。本篇形成时，一般森林的已证上界是 $O(n^2+m+nN\log(n+1))$；这里给出一个依赖分枝分布的补充界，进一步扩大已证明三次方的范围。$N$ 是道路格数，$W$ 是实际候选检查次数，包含成功和失败检查。重复位移和直接越界清空不增加 $W$。 **本篇结束时的状态：**末节的真实完整前缀周期族，已否定按历史第三长臂容量支付全部重复标记的逐配对和聚合猜想。死亡时间、短臂窗口及带显式余项的归约仍然成立；一般复杂度问题尚未解决。 ## 结论 对道路分量 $C$ 内的点 $x$，沿它的每个邻接方向，取该方向所能到达的最远点到 $x$ 的树距离。将这些方向高度从大到小排序，令 $t_C(x)$ 为第三个高度；不足三个方向时取零。对整数 $r\ge1$，记 $$ b_r(C)=|\{x\in C:t_C(x)\ge r\}|, \qquad \beta_s=2s^2+2s+1. $$ 那么任意查询都有 $$ \boxed{W\le\beta_{r-1}(6n-5)N+\sum_C |C|b_r(C).} $$ 特别地，令 $B_C$ 为分量中度数至少为三的点数，则 $$ \boxed{W\le(6n-5)N+\sum_C |C|B_C.} $$ 因此，每个道路分量只有 $O(n)$ 个分叉点时，任意长度的枝条和任意查询顺序都满足 $O(n^2+m+nN)$。更一般地，只要存在固定常数 $r$，且每个分量中能向三个方向各延伸至少 $r$ 步的点只有 $O(n)$ 个，同样有这个结论。 对每个道路分量，分枝深度还满足 $$ \sum_{r\ge1}b_r(C)=\sum_{x\in C}t_C(x)\le |C|-1. $$ 这些参数界尚未消去一般森林上界中的对数。 ## 首次出现分叉之后 先证明 $r=1$ 的结论。只考虑最后仍有候选存活的完整查询树 $T$；最终使全部候选失败的新位移不属于它。 在 $T$ 的生长过程中，取第一次出现度数至少为三的点的时刻，记这个点为 $q$。这个时刻以前的查询前缀是一条路径，查询根可以在其中间。由[根叶链证明](complexity-chains.zh.md)，对任意目标道路格 $v$，前段至多有 $6n-6$ 次成功命中。 从这一轮起（包括这一轮），若新位移 $p$ 对应的起点 $v-p$ 成功，则整个当前前缀都在道路上。特别是，$q$ 及其三条已经访问的邻边被映到 $$ v+q-p. $$ 所以这个点是 $v$ 所在分量的分叉点。不同的新位移 $p$ 映到不同的点，故后段命中 $v$ 的次数至多为 $B_C$。如果整个有效查询没有分叉，后段为空。因此 $$ H(v)\le6n-6+B_C. $$ 每个起点至多失败一次，失败总数不超过 $N$。对所有目标求和，便得到第二个方框中的界。这里固定的是首次分叉时已经完整访问的三条边，不需要等待查询的其他分枝完成。 ## 三条长臂与直径外的深度 在一棵树中，称以 $x$ 为中心的三条长度均为 $r$、除中心外互不相交的简单路径为一个长度 $r$ 的三臂结构。它存在当且仅当 $t(x)\ge r$。 取树的任意一条直径路径 $D$。有如下精确等式： $$ \max_{p}\operatorname{dist}(p,D)=\max_x t(x). $$ **第一方向。** 设 $p$ 到 $D$ 的距离为 $d$，连接点为 $q$，直径两端为 $u,w$。路径 $p$ 到任一直径端点的长度不能超过直径，因此 $$ d\le\operatorname{dist}(q,u),\qquad d\le\operatorname{dist}(q,w). $$ 当 $d>0$ 时，从 $q$ 通向 $p,u,w$ 的三个方向均可走至少 $d$ 步，所以 $t(q)\ge d$。 **第二方向。** 任意简单路径至多进入某个三臂结构的两条臂。若该路径不经过中心，它整体位于删去中心后的某个分量内。两种情况下，总有一条长度 $t(x)$ 的臂，其端点到该路径的距离至少为 $t(x)$。对 $D$ 应用这个事实，得到另一个方向。 所以，不含长度 $r$ 三臂结构的树，其所有点到任一直径路径的距离都至多为 $r-1$。 ## 在第一组三条长臂处分段 取有效查询首次含有长度 $r$ 三臂结构的时刻，并固定这组三臂及中心 $q$。后段从这一轮开始，包含这一轮。若不存在该时刻，就把整个有效查询作为前段，后段为空。 前段的最后一个完整查询树不含这种结构，因此在某条直径路径的距离 $r-1$ 以内。以查询根为根，取直径路径加上根到它的连接作为核心，核心至多有两片有根叶。每个点到其最后一个核心祖先的距离仍不超过 $r-1$。 应用[短分枝投影证明](complexity-chains.zh.md)，若前段有 $S_{\mathrm{early}}$ 次成功检查，则 $$ N+S_{\mathrm{early}}\le\beta_{r-1}(6n-5)N. $$ 这里保留 $N$ 个初始配对：投影证明直接控制的是初始配对与成功配对之和，而不仅是实际检查数。 后段中，任一成功命中 $v$ 的位移 $p$，都会把固定的完整三臂结构映入道路分量。因此 $v+q-p$ 满足 $t_C(v+q-p)\ge r$。同样利用新位移互不相同，后段在目标 $v$ 上至多成功 $b_r(C)$ 次。结合全部失败检查至多为 $N$，得到 $$ W\le N+S_{\mathrm{early}}+\sum_C |C|b_r(C) \le\beta_{r-1}(6n-5)N+\sum_C |C|b_r(C). $$ 空道路图、单点分量和单点查询均兼容这个界。越界清空没有检查；最后全失败的一轮由失败项支付，无需放入有效查询树。 还可以按起点所在分量拆分检查量。对每个分量单独取最后仍在该分量有候选存活的前缀，再独立选取阈值，得到 $$ W\le\sum_C |C|\min_{r\ge1}\{\beta_{r-1}(6n-5)+b_r(C)\}. $$ 这是分别应用证明后求和；各分量的分段时刻无需相同。 ## 分枝深度的总预算 在道路分量中任取根。每个有子节点的点，选择能向下走得最远的一个子节点，其边标为重边；其他子边标为轻边。 若 $t_C(x)>0$，至少有两个子方向的高度不小于 $t_C(x)$：三个长方向中，至多一个是父方向。因此可以选择一个这样的轻子边，从 $x$ 沿它走一步，再沿重边继续，共走 $t_C(x)$ 步。 不同 $x$ 得到的这些路径边不相交。每条路径的第一条边是不同的轻边，余下部分位于该轻边进入的重链中；一条重链只有一个来自外部的父轻边。路径可以共享端点，但不能共享边。 用分量的 $|C|-1$ 条边支付这些路径，得到 $$ \sum_x t_C(x)\le |C|-1. $$ 最后按高度逐层计数，即得开头的预算等式，也有 $b_r(C)\le(|C|-1)/r$。把这个粗界代入主定理，并不能超过已有的一般对数上界；它主要用于描述哪些道路分量已经满足三次方界，以及继续研究各深度之间能否共享计费。 ## 已访问连通子模板之外的平衡挂枝 可以把后续成功检查分散到宿主各点的第三长臂，而不乘以最长挂枝长度。设 $T$ 为最后有效查询树，截断时刻之前的全部成功检查数为 $S_{\mathrm{early}}$。选取非空连通子模板 $P\subseteq T$，要求此时已经访问了它的所有点。它不必等于整个已访问前缀，也不必包含查询根。 删除子模板后，每个剩余分量通过唯一一条边挂到子模板。对 $q\in P$，记这些经它挂接的点的并集为 $B_q$，不含附着点本身。令 $$ L_q=\max_{x\in B_q}\operatorname{dist}_T(q,x),\qquad V_q(r)=|\{x\in B_q:\operatorname{dist}_T(q,x)\le r\}|. $$ 空挂枝不需满足条件。对每个非空挂枝，假设子模板内从附着点出发的两个不同方向都能走至少 $L_q$ 步，并且对每个正整数半径有 $$ V_q(r)\le\lambda r. $$ 两个方向的高度必须分别足够，不能只比较它们的和。记子模板包围盒的高、宽为 $h_P,w_P$，令 $$ b(P)=h_P+w_P-1\le2n-1. $$ 道路森林有 $c$ 个非空分量，则截断后的成功检查满足 $$ \boxed{ S_{\mathrm{tail}} \le\lambda b(P)\sum_{z\in F}t_F(z) \le\lambda b(P)(N-c). } $$ 全程每个起点最多失败一次，所以 $$ \boxed{ W\le N+S_{\mathrm{early}}+\lambda b(P)(N-c). } $$ 前段必须计入截断前的全部成功，包括子模板之外已经访问的点；失败项全程只加一次。 ### 同一候选与附着点只支付一次 固定候选起点与附着点 $(a,q)$。若它在该挂枝中有后续成功，令最大成功深度为 $s$。达到该深度时，真实完整前缀已包含整个子模板。已访问集合连通，且最终查询为树，因此也含有从附着点到成功点的整条路径。 平移后，宿主点 $z=a+q$ 处存在三条仅交于中心的路径：两条来自已访问子模板，各长至少 $L_q\ge s$；第三条来自挂枝，长为最大成功深度。因此 $$ s\le t_F(a+q). $$ 该候选在这个挂枝中的全部后续成功点都落在深度球内，故总贡献至多为 $$ V_q(s)\le\lambda s\le\lambda t_F(a+q). $$ 这使用一次真实历史成功证书；候选以后被删除不影响证明。任意多次交错访问也不重复收费。 再固定宿主点。每个可能的附着点唯一确定候选起点，且该候选已经匹配过整个子模板。定义全部合法平移为 $$ \mathcal A(P)=\{a\in\mathbb Z^2:a+P\subseteq F\}. $$ 相应附着点位于固定完整模板的静态锚点集合 $$ \{q\in P:z-q\in\mathcal A(P)\}, $$ 其大小至多为 $b(P)$。子模板不含原查询根也无妨：把其中任一点平移为原点，锚点计数及包围盒不变。对各宿主点求和，再使用第三长臂总预算，即得两个方框中的结论。 若各附着点的增长率不同，也有加权形式 $$ S_{\mathrm{tail}} \le\sum_{z\in F}t_F(z) \sum_{\substack{q\in P\\z-q\in\mathcal A(P)}}\lambda_q. $$ 没有剩余挂枝的点可取零增长率。该公式仍固定同一个子模板，未解决更换子模板后的资源复用。 ## 先完成直径，再任意增长路径挂枝 由新尾段界得到一个不限制挂枝长度的三次方子类。假设最终有效查询树有一条直径路径 $P$，删除它后每个分量都是路径。查询根可以任取；要求先完整访问直径及根到直径的必要连接路径，然后才访问其余点。后续挂枝可任意交错增长。 直径性质保证高度平衡。若端点为 $u,v$，挂枝点经附着点接入，深度为 $s$，则 $$ s+\operatorname{dist}_P(q,u)\le |E(P)|,\qquad s+\operatorname{dist}_P(q,v)\le |E(P)|. $$ 所以每条直径臂的长度都至少为挂枝深度。 此外可以统一取 $\lambda=2$，即使连接边落在某个路径分量的内部点： - 只有一个挂枝分量时，深度球内至多有 $2r-1$ 个点。 - 有两个挂枝分量时，附着点的道路度数为四。任一入口若向侧面转弯，会与附着点的另一相邻道路构成单位四环，因此入口必须是其路径分量的端点。两个分量各至多贡献 $r$ 个点。 前段实际访问集合是直径加根到它的连接，以原查询根定根后至多有两片叶。由根链界，前段成功至多为 $6(n-1)N$。尾段收费仍选原直径作为子模板；根在直径外时，根外侧的剩余路径仍归入它在直径上的附着点，不把根误当作只有一条核心臂的收费中心。合并得到 $$ \boxed{ W\le N+6(n-1)N+2(2n-1)(N-c) \le(10n-7)N. } $$ 于是该类查询在任意道路森林上的时间为 $O(n^2+m+nN)$。直径和挂枝都可以弯曲，挂枝长度无需有常数上界。先完成指定连接路径和直径的顺序要求仍不可省略；本证明没有控制未建立两条完整臂时的费用。 ## 固定子模板的范围 同一个固定子模板下，尾段可以分任意多批，最大成功深度只统计一次。对于一般分枝，不能把每批新增点数直接写成增长率乘最大深度增量，因为后来可能补入另一分枝的浅层点；上面的整球计数避免了这个问题。 增长率条件也不能删除。一棵平衡挂枝可在高度和宽度都线性的范围内放入二次方数量的梳齿点；若全部投影到一个附着点，其第三长臂仅为线性长度，费用不足。更一般的证明需要使用挂枝内部的分叉资源，并控制扩大子模板时新增附着锚点的重复使用。一般森林的对数缺口仍未消除。 ## 任意顺序下的直径与分叉费用 仍假设最终有效查询树 $T$ 删去一条直径 $P$ 后各分量都是路径，现在允许任意根和任意连通发现顺序。下面支付全部分叉费用，留下一个尚未控制的直径项。 对每个初始候选 $a$，令 $T_a$ 为它最后成功匹配的完整前缀；第一次新点就失败时取单点树。若成功检查总数为 $S$，则 $$ S=\sum_a(|T_a|-1),\qquad W\le N+S=\sum_a|T_a|. $$ ### 树体积的分解 对任意最大度至多四的有限树 $R$，记度数为 $d_R(q)$、以边数计的直径为 $D(R)$。有 $$ \boxed{|R|-1\le D(R)+\sum_{q\in R}(d_R(q)-2)_+t_R(q).} $$ 其中 $(x)_+=\max(x,0)$。证明时，以任一直径的端点为根；在直径上选择通往另一端的子边为重边，在其他点选择向下高度最大的子边。其余子边为轻边。 直径性质保证，每个非根点的父方向至少与它的任一轻子方向一样高。对直径外的点，设其到直径的距离为 $s$，投影点距直径两端为 $A,B$，某子方向高度为 $h$。则 $$ s+h\le\min(A,B), $$ 而父方向高度至少为 $s+\max(A,B)$。直径上的点则直接使用两侧臂长的平衡。 每条轻边及其后续重链组成一条路径，长度恰为该轻子方向的高度。它不超过父点的第三长方向高度，因为父方向和重子方向也至少这么长。这些路径恰好划分直径外的边；每个点至多有 $(d_R(q)-2)_+$ 条轻子边，得到方框中的不等式。单点树也成立。 ### 历史锚点的重数 令 $B=6n-5$。固定宿主点 $z$，所有满足 $$ q\in P\cap T_a,\qquad a+q=z $$ 的历史配对至多有 $B$ 个。原因是直径及原根到直径的连接以原根定根后至多有两片叶。直径上的点包含在两条原根链中，每条链的非初始成功至多为 $3(n-1)$，另加最多一个初始配对。这使用各候选真正成功过的前缀，不要求它们匹配完整直径。 直径外的分叉只可能是路径分量的内部入口 $e$，它邻接唯一的直径点 $q$，度数为三。当 $t_{T_a}(e)>0$ 时，三个邻点都在该成功前缀中，因此直径邻点也已成功。按单位方向 $e-q$ 分为四类，每一类注入目标 $z-(e-q)$ 上的直径历史配对。故固定宿主点上的此类入口配对至多为 $4B$。 将体积不等式用于每个候选。直径上的系数至多为二，外部入口的系数至多为一，并且 $$ t_{T_a}(q)\le t_F(a+q). $$ 因此 $$ W\le N+\sum_a D(T_a)+6(6n-5)(N-c). $$ 若每个路径分量都从端点接入直径，没有外部内部入口，则系数六可改为二。 ### 直径项是哪些真实检查 令 $T_i$ 为加入第 $i$ 个有效新位移后的完整前缀。新增一个叶子时，直径增长零或一，定义 $$ \Delta_i=D(T_i)-D(T_{i-1})\in\{0,1\},\qquad S_D=\sum_{i:\Delta_i=1}|A(T_i)|. $$ 这里使用本轮筛选后的候选数，所以统计的是成功检查。按候选交换求和，有精确等式 $$ \sum_aD(T_a)=\sum_i\Delta_i|A(T_i)|=S_D. $$ 最终得到任意发现顺序下的严格归约 $$ \boxed{W\le N+S_D+6(6n-5)(N-c).} $$ 若所有路径分量从端点接入，则 $$ \boxed{W\le N+S_D+2(6n-5)(N-c).} $$ 还可改用根高度。令 $H(T_i)$ 为原根到最远点的树距离，令 $S_H$ 统计首次达到新根深度时的成功检查。同样有 $$ \sum_aH(T_a)=S_H,\qquad S_D\le2S_H. $$ 若能证明其中任一记录总量为 $O(nN)$，就能去掉前一子类的访问顺序要求。目前这一项仍未受控：树直径可能为 $\Theta(n^2)$，记录点也可能在不同根链之间切换。上面的归约没有证明任意顺序的三次方上界。全部失败仍只计一次，最后全失败点和旧点回访均按前述方式处理。 ## 补齐局部分叉不会简化一般局部命中问题 对任意真实执行，令 $J(z)$ 计数满足以下条件的历史配对：中心 $q$ 是最终查询的分叉点，候选 $a$ 的最后成功前缀含该中心及至少三个邻点，且 $a+q=z$。普通局部成功数记为 $H(v)$。显然 $$ J(z)\le H(z)+1. $$ 反向也有常数尺度归约。令 $$ C=\{(0,0),(1,0),(-1,0),(0,1),(0,-1)\},\qquad F^\star=\bigcup_{x\in F}(3x+C). $$ 每个原点替换为一个五点十字。非相邻原点的十字之间距离至少为四；相邻原点的十字之间恰有一条单位边。因此每条原边变成三步走廊，中心原来缺少的方向变成新叶。新图仍为诱导森林，且 $$ N^\star=5N,\qquad |E(F^\star)|=5N-c,\qquad n^\star\le3n. $$ 先把原查询截到最后有效前缀，再将每步替换为同方向三步。初始中心以及每个首次到达的新中心，都先往四个单位方向各走一步再返回。若原截断步序长度为 $m_0$、不同点数为 $k$，得到真实连续步序 $$ m^\star=3m_0+8k. $$ 候选 $3a$ 完成一个新查询块，当且仅当候选 $a$ 匹配对应旧前缀。正向由全部十字和走廊合法得到；反向使用两个坐标同时为三的倍数的道路点必为十字中心。一个中心合法时，四次巡叶也都合法。 于是每个原成功配对都变成完整四邻点已匹配的中心配对，并保留固定目标： $$ (a,p)\longmapsto(3a,3p),\qquad J_{F^\star}(3v)\ge H_F(v). $$ 因此，对全部实例证明 $J(z)=O(n)$ 与证明一般的 $H(v)=O(n)$ 经常数尺度等价。完整局部分叉证书仍可作为工具，但单独加入它没有降低这个局部问题的难度。两种一般局部界目前都未证明。 ## 根高度记录的重复水平标记 还有一条利用记录时间序的严格结构。固定道路目标 $v$；称首次达到一个此前未出现的查询根深度、且起点 $v-p$ 成功的新位移 $p$ 为一个成功根高度记录。可以把根 $p=0$ 另算为初始记录，至多增加一个点。 取若干点对 $(e_i,f_i)$，要求两端都是同一目标的成功根高度记录，$e_i$ 先于 $f_i$，并且 $$ f_i-e_i=\delta $$ 是同一个非零水平向量。这个向量同时固定长度和访问方向。不同点对必须位于不同查询行。由已有的时间平行四边形禁形，两个标记区间既不能分离，也不能交错，只能严格嵌套。按区间从外到内编号，得到 $$ e_1s_{i+1}-x_{i+1}. $$ 因此 $$ \boxed{x_{i+1}-x_i>|s_{i+1}-s_i|.} $$ 各量均为整数，逐项相加还得到根段长度的总变差界 $$ \sum_{i=1}^{r-1}|s_{i+1}-s_i| \le x_r-x_1-(r-1). $$ 同一对中早端深度小于晚端深度，故 $\ell-2x_i>0$。结合整数性，有 $$ \boxed{0\le x_10$ 且 $s_i>0$ 时，投影点存在三个不同方向的臂，长度至少为 $x_i$、$\ell-x_i$、$s_i$，从而 $$ t_F(z_i)\ge\min\{x_i,s_i\}. $$ 最多一个标记可以有 $x_i=0$；可以有多个 $s_i=0$，后一类不能直接用第三长臂支付。 这些结论只针对固定目标、固定水平向量、不同查询行中的一个标记族。这样的族本来就至多有 $n$ 个成员，路径长 $\ell$ 却可能达到 $\Theta(n^2)$。不同标记族和不同目标可以重复使用同一根段，目前没有全局重数界。因此不能直接把单族预算对所有标记相加，也尚未由此证明 $S_H=O(nN)$。 ## 高度记录需要任意多根链的梳形族 取整数 $k,H\ge1$，坐标为行、列，令查询与宿主都是以下诱导树，根为左上端点： $$ F=Q=\{(0,c):0\le c\le2k\} \cup\{(t,2i):1\le t\le H,\ 0\le i\le k\},\qquad r=(0,0). $$ 各竖齿之间留一整列空格，只有主干将它们连接，因此没有额外邻接或环。从左到右逐齿走到底，再返回主干继续，最后停在最右齿尖。全部首次发现前缀都有原根参考副本，真实点数、边长和步数为 $$ N=2k+1+(k+1)H,\qquad n=\max(2k+1,H+1),\qquad m=2k+(2k+1)H. $$ 固定目标 $v=(H,2k)$。第一齿的每个点都是高度记录，其当前竖段可平移到最右齿末端。以后每个齿尖也都是记录，其完整前缀可平移到宿主右侧的子梳。其他记录不能命中此目标：将后续齿内部点或主干点送到目标，会使此前已经完整访问的第一齿越过最底行。因此 $$ H_H(v)=H+k,\qquad \text{minimum root-chain cover}=k+1. $$ 第二式来自所有齿尖互不可比，且每条根到齿尖的路径足以覆盖该齿上的记录。故高度记录不能总由固定常数条原根链覆盖。 精确计数也很直接。第一齿每深入一步后的幸存候选数依次减少一个齿数；之后每到下一段奇列主干，删除最右起点，再直到该齿完成都不删候选。后续每个块恰有两个高度记录，齿长一时也成立。对这些块求和得 $$ \begin{aligned} W&=N+(k+1)\left(\frac{H(H+1)}2-1\right) +(H+2)\frac{k(k+1)}2+k,\\ S_H&=(k+1)\frac{H(H+1)}2+k(k+1). \end{aligned} $$ 取 $H=2k$，得到 $$ \begin{aligned} n&=2k+1,&N&=2k^2+4k+1,&m&=4k^2+4k,\\ W&=3k^3+7k^2+6k,&S_H&=2k(k+1)^2,&H_H(v)&=3k. \end{aligned} $$ 所以记录成功总数本身可达 $\Theta(nN)=\Theta(n^3)$，局部记录数除以边长趋于 $3/2$。这些是三次方与线性的下界，仍未超过待证上界；一般记录总量问题仍然开放。 ## 把重复记录标记归到真实分叉配对 下面给出一个精确归约，不要求先完成直径。它把不能由行数和水平标签数支付的记录，分给真实成功前缀中的分叉点。尚未控制同一个配对被收费的次数，因此这还不是一般三次方证明。 ### 第一子边分组与最早行星心 令 $T$ 为最后有效查询树。固定目标 $v\in F$，令 $S_v$ 为其成功根高度记录集合，排除初始根。每个记录都要求候选 $v-p$ 成功匹配该点出现时的完整实际前缀。最终全失败的新点不贡献 $S_H$，重复位移仍只计入真实移动数 $m$。 按照从原查询根到记录点的第一条子边，把集合分成至多四组。对每组的每个非空查询行，取首次发现最早的记录 $e$ 为星心，给该行每个其他记录 $f$ 建立标记。其标签为有符号水平向量 $\delta=f-e$。 这样星心必先于晚端，每个非星心记录恰好是一个标记的晚端；每组每行对同一标签至多产生一个标记。取最早记录而非几何最左点，是为了避免一个后来出现的星心成为多条边的共同晚端，从而重复计算同一次成功。 有效查询能整体平移进宿主，所以至多占用 $n$ 行。每组的非零有符号水平向量至多有 $2(n-1)$ 种。 ### 每个标签只留最外层免费 固定一组和一个标签。不同标记位于不同行，其时间区间严格嵌套。只保留最外层为免费标记，其余称为收费标记。记目标处的行星心数、免费标记数、收费标记数分别为 $R_v,L_v,C_v$，则 $$ |S_v|=R_v+L_v+C_v,\qquad R_v\le4n,\qquad L_v\le8(n-1). $$ 因此 $$ \boxed{H_H(v)=|S_v|\le12n-8+C_v.} $$ 取一个收费标记 $(e,f)$，定义 $$ a=v-f,\qquad q=\operatorname{LCA}_T(e,f). $$ 它是同标签的内层标记，所以前述严格投影引理给出 $$ \operatorname{dist}_T(e,q)>0. $$ 又因为记录深度随时间严格增加，有 $q\ne f$。两端属于同一第一子边组，故 $q\ne0$。晚端成功时，候选已经匹配查询根、两端和它们之间的全部路径，因此收费点的父方向与两个不同子方向都已存在。 令 $T_a$ 为候选的最后成功前缀，就得到真实历史证书 $$ \deg_{T_a}(q)\ge3,\qquad t_{T_a}(q)\ge \min\{\operatorname{depth}_T(q),\operatorname{dist}_T(e,q)\}\ge1. $$ 候选后来失败不会撤销证书。第一子边分组排除了查询根只有两个方向、无法得到第三长臂的情况。 ### 收费重数的精确定义 令 $M(a,q)$ 为跨全部目标、归到同一候选起点和同一查询 LCA 的收费标记总数。每个标记晚端对应一次实际成功 $(a,f)$，其目标由 $v=a+f$ 唯一确定；在该目标内，晚端又只有一个标记。因此没有把一次实际成功分给多个收费标记。 由定义精确有 $$ \sum_v C_v=\sum_{a,q}M(a,q), $$ 从而 $$ \boxed{S_H\le(12n-8)N+\sum_{a,q}M(a,q).} $$ 非零重数只出现在候选的真实历史分叉上。至此的归约适用于任意诱导网格森林查询。 ### 路径挂枝子类的已有容量 再假设最终查询删除一条直径 $P$ 后，每个分量都是路径。记宿主非空分量数为 $c$，并令 $B=6n-5$。定义不乘度数系数的历史容量 $$ \Psi=\sum_a \sum_{\substack{q\in T_a\\\deg_{T_a}(q)\ge3}} t_F(a+q). $$ 动态锚点计数给出 $$ \boxed{\Psi\le5B\sum_{z\in F}t_F(z) \le5(6n-5)(N-c).} $$ 其中主干上的配对，在固定宿主点的重数至多为 $B$：直径包含在至多两条原根链之并内，再容许一个初始配对。主干外的分叉只能是相邻的路径内部入口。入口成为前缀分叉时，相邻主干点必已成功；按四个入口方向，注入其邻点的历史锚点集合，重数至多为 $4B$。 这不要求查询根位于直径上，也不要求某时刻已经完整匹配直径。若所有路径挂枝均从其端点接入，则没有外部内部入口，容量界中的系数五可改为一。 曾考虑以绝对常数 $C$ 建立下面的容量关系： $$ \sum_{a,q}M(a,q)\le C\Psi, $$ 若该关系成立，上述归约就会给出这一子类的 $S_H=O(nN)$。但末节的周期族已经严格否定这个不等式，也否定更强的逐配对界 $M(a,q)\le C t_F(a+q)$。第三长臂证书与此前的有效归约仍然保留；它们不能支付不同标签和不同目标的全部重复收费。 ## 外层标记给出的死亡时间与短方向收费 本节继续使用上述精确收费定义。它控制早、晚端中至少一个方向较短的全部收费；两条长方向之间的收费仍未解决。 ### 外层候选根的精确距离 固定目标 $v$，取内层收费标记 $(e,f)$ 及任一同标签外层 $(e',f')$。其发现时间与位移满足 $$ e'0,\qquad D_f=\operatorname{depth}_T(f')-\operatorname{depth}_T(f)>0. $$ 两次完整晚端成功使平移后的端点路径成为同一宿主路径 $R$，端点为 $v-h,v$，长度为 $\ell=x+y$。把外层的对应 LCA、根深和早端距离记为 $q',s',x'$，则端点深度关系给出 $$ x-x'=\frac{D_e+D_f}{2}>0,\qquad s'-s=\frac{D_f-D_e}{2}. $$ 令 $z=a+q$、$z'=b+q'$。它们分别是候选根到 $R$ 的投影；后者位于前者朝向 $a+e$ 的一侧，距离为 $x-x'$。不同投影的根段彼此不交，并且除投影外均在公共路径之外。因此 $$ \operatorname{dist}_F(a,b)=s+(x-x')+s'=2s+D_f, $$ $$ \boxed{\operatorname{dist}_F(z,b)=(x-x')+s'=s+D_f.} $$ 特别地，$b$ 位于从 $z$ 通向早端的那个方向分量。若该方向的最大高度为 $B_E$，就有 $$ s+D_f\le B_E. $$ 这些等式不要求内层候选后来继续存活。 ### 内层晚端候选必在外层晚端前失败 这一事实只需要四次相应的完整前缀成功，不依赖高度记录或最早星心的额外条件。 平移坐标令 $a=0$，并记 $$ d=e-e'=f-f',\qquad h=f-e=f'-e'. $$ 由于两标记不同行，$d$ 非水平，所以 $\det(d,h)\ne0$。反设零点候选仍存活到 $f'$。令 $P_p$ 表示首次发现点 $p$ 时的完整实际前缀。基准候选、外层晚端候选和内层早端候选分别给出 $$ P_{f'}\subseteq F,\qquad P_{f'}+d\subseteq F,\qquad P_e+h\subseteq F. $$ 取查询有向路径 $U:e'\to e$、$V:e'\to f'$。两者都在基准完整前缀中，且 $U\subseteq P_e$，故宿主含有四条路径 $$ U,\qquad V,\qquad U+h,\qquad V+d. $$ 它们按下面的顺序组成闭游走： $$ U,\quad V+d,\quad -(U+h),\quad -V, \qquad e'\to e\to f\to f'\to e'. $$ 不要求四段内部互不相交。对有向路径 $L=(z_0,\ldots,z_k)$，定义面积和及其平移公式 $$ \mathcal A(L)=\sum_{i=0}^{k-1}\det(z_i,z_{i+1}),\qquad \mathcal A(L+t)=\mathcal A(L)+\det(t,z_k-z_0). $$ 上述闭游走的面积和于是为 $$ \mathcal A(U)+\mathcal A(V+d)-\mathcal A(U+h)-\mathcal A(V) =\det(d,h)-\det(h,d)=2\det(d,h)\ne0. $$ 森林闭游走沿每条边正反经过次数相等，面积和必为零，矛盾。因此候选必在外层晚端之前失败。 这里失败的是完整前缀匹配。事实上 $a+f'$ 已由早端副本提供为道路点；失败可以发生在此前的其他新点，不能把结论改成该单点不是道路。特别地，存活到最终有效前缀的候选不会接收任何收费标记。 ### 所有外层标记共享同一个最后高度窗口 令 $H_a$ 为候选最后成功前缀 $T_a$ 的原根高度。内层晚端成功，而外层晚端是更晚的全局高度记录，所以即使首次失败发生在非记录点，仍有 $$ \operatorname{depth}_T(f)\le H_a <\operatorname{depth}_T(f') =\operatorname{depth}_T(f)+D_f. $$ 等价地， $$ H_a-D_f<\operatorname{depth}_T(f)\le H_a. $$ 不同收费可以选用不同外层，但共享同一个 $H_a$。若一组收费都有 $D_f\le D$，则这整组至多有 $D$ 笔：每个全局记录深度只有一个记录点，固定候选的每个晚端又只收费一次。无需再按标签或星心相乘。 ### 短方向部分的总收费 固定一个收到收费的配对，令 $$ z=a+q,\qquad t=t_F(z),\qquad s=\operatorname{depth}_T(q)\ge1. $$ 对每笔收费，以 $B_E,B_F$ 表示从该宿主点分别通向早、晚端的两个不同子方向的最大高度。 若 $B_F\le t$，其晚端记录深度属于 $s+1,\ldots,s+t$，所以所有这类收费合计至多 $t$ 笔。 若 $B_E\le t$，前述精确根距给出 $1\le D_f\le t-s$。共同最后窗口于是使所有这类收费合计至多 $\max(0,t-s)$ 笔；这里已经包括同一星心对应多个晚端的情况。 令 $M_{\mathrm{LL}}(a,q)$ 只计两个方向都严格长于第三长臂的收费，即同时满足 $B_E>t$ 和 $B_F>t$。将前两类的上界相加，严格得到 $$ \boxed{M(a,q)\le t+\max(0,t-s)+M_{\mathrm{LL}}(a,q) \le2t+M_{\mathrm{LL}}(a,q).} $$ 宿主点至多有两个方向严格长于其第三长方向。因此剩余收费只能使用同一对长方向，至多有正反两种选择。查询父方向较短，并且已经包含长度为 $s$ 的根段，故 $$ M_{\mathrm{LL}}(a,q)>0\ \Longrightarrow\ s\le t. $$ 特别地， $$ \boxed{\operatorname{depth}_T(q)>t_F(a+q) \ \Longrightarrow\ M(a,q)\le t_F(a+q).} $$ 上述分类适用于一般查询。对于直径外分量都是路径的子类，短方向部分求和至多为 $2\Psi$，可用前面的容量界支付。尚未证明的是 $M_{\mathrm{LL}}$ 的累计界；本节没有把这个剩余部分视为已付，也没有由此宣称一般三次方复杂度。 ### 还可按实际早端臂长缩小余项 精确投影式中 $x'\ge0$，而较早记录的深度差满足 $D_e\ge1$，所以 $$ D_f=2(x-x')-D_e\le2x-1. $$ 因此，对固定配对，所有实际早端距离满足 $x\le t$ 的收费，无论宿主该方向还能伸多远，都落在最后 $2t-1$ 个高度记录内。令 $M_{x>t}(a,q)$ 只计实际早端距离较长的收费，就得到另一条严格上界 $$ \boxed{M(a,q)\le2t-1+M_{x>t}(a,q).} $$ 它保留了更小的未解集合；前面的短方向细分式仍可给出更精细的已付费用。剩余收费的实际两条子臂都长于第三长臂，父方向因而较短，严格满足 $$ s\le tt}(a,q),\qquad B=6n-5. $$ 已证明的部分可以直接合并为 $$ \sum_{a,q}M(a,q)\le2\Psi+R_{\mathrm{rem}},\qquad S_H\le(12n-8)N+2\Psi+R_{\mathrm{rem}}. $$ 代入前述体积分解和容量界，得到精确的未完成收费归约 $$ \begin{aligned} W&\le N+S_D+6B(N-c)\\ &\le N+2S_H+6B(N-c)\\ &\le (24n-15)N+4\Psi+6B(N-c)+2R_{\mathrm{rem}}\\ &\le\boxed{(24n-15)N+26(6n-5)(N-c)+2R_{\mathrm{rem}}}. \end{aligned} $$ 这说明除了明确列出的总余项，其他费用已经是三次方量级。仍需证明或否定该余项的相应界，才能完成这个查询子类的任意顺序分析。真实移动数仍另加输入处理费用。 ## 周期族反例：历史第三长臂总容量不能支付全部标记 下面给出保留真实完整前缀和最早星心定义的反例族。取三的倍数 $H\ge12$，可构造 $$ n=H+5,\qquad N=9H+14,\qquad |T|=6H+2, $$ 以及一个固定候选和固定查询分叉，使 $$ M(\widehat a,\widehat q)\ge\frac H3,\qquad t_F(\widehat a+\widehat q)=3,\qquad \Psi=9. $$ 查询删除直径后只剩一条长度三的路径。因此反例已经位于此前希望处理的路径挂枝子类。它同时否定逐配对和聚合容量猜想，但不是原算法扫描量的超三次方反例。 ### 查询与真实发现顺序 本构造使用几何坐标 $(x,y)$，向北表示第二坐标加一。令 $$ U=\mathsf N^H\mathsf E^2\mathsf S^{H-2}\mathsf E^2, \qquad L=|U|=2H+2. $$ 这个路径词的净位移为 $(4,2)$。取主干点 $q=(0,0)$，向正侧沿两次该词的前缀延长，向负侧沿一次逆词的前缀延长。添加短挂枝 $$ q\to(0,-1)\to r=(0,-2)\to(-1,-2), $$ 并以 $r$ 为原查询根。先访问左叶，再经根连接到主干；之后按下列顺序发现新点，每次换分支都沿已经访问的树真实往返。 1. 正臂先向上到 $(0,H)$。 2. 对 $y=H-3,H-6,\ldots,3$，先延长负臂到 $e_y=(-4,y)$，再延长正臂到 $f_y=(2,y)$。 3. 最后继续正臂，直到第二个周期内的 $(6,5)$。 最终主路径从 $(-4,3)$ 经主干点到 $(6,5)$，两侧长度分别为 $2H-3$ 和 $4H+1$。它是一条直径，外面只有上述短挂枝。查询唯一的度三点是主干点，原根自身度数为二。 为与前文根为零的候选定义一致，归零后记 $$ \widehat q=q-r=(0,2),\qquad \widehat a=r=(0,-2),\qquad \widehat b=r+(-4,-2)=(-4,-4). $$ 后面写出的几何查询点和副本平移仍用归零前坐标；它们在宿主中的位置不变。 ### 四份完整前缀及诱导树证明 记最终前缀为 $P_*$，全部内层轮次完成后的前缀为 $P_f$，最后一次到达负臂末端后、最后一次正臂增长前的前缀为 $P_e$，初始向上走完的前缀为 $P_0$。定义宿主 $$ F=(P_*+(-4,-2))\cup P_f\cup(P_e+(6,0))\cup(P_0+(2,-2)). $$ 每份前缀都包括初始左叶、根连接以及全部此前发现的分支。宿主也可以精确分解成下面的折线路径、一个额外分支和三个短挂枝。相邻拐点之间包括全部整数点。 主路径为 $$ \begin{gathered} (-8,1)\to(-8,H-4)\to(-6,H-4)\to(-6,-2)\to(-4,-2)\\ \to(-4,H-2)\to(-2,H-2)\to(-2,0)\to(0,0)\\ \to(0,H)\to(2,H)\to(2,-4)\to(1,-4). \end{gathered} $$ 在 $J=(2,H-2)$ 加分支 $$ J\to(4,H-2)\to(4,0)\to(6,0)\to(6,H)\to(8,H)\to(8,6), $$ 再加三个长度三的短挂枝 $$ \begin{gathered} (-4,-2)\to(-4,-4)\to(-5,-4),\\ (0,0)\to(0,-2)\to(-1,-2),\\ (6,0)\to(6,-2)\to(5,-2). \end{gathered} $$ 长竖段位于相隔两列的偶数列；水平连接仅在列出的高度出现。不同高度的横段至少隔两行，同高但不相接的横段之间保留空列；短挂枝的左叶也保留空格，因此没有额外四邻接。主路径、侧分支和三个短挂枝的边数分别为 $6H+6$、$3H-2$、$9$，所得诱导图是一棵树，点数确为 $$ N=(6H+6)+(3H-2)+9+1=9H+14. $$ 坐标范围为 $[-8,8]\times[-4,H]$，所以方框边长为 $H+5$。 ### 一般参数下的真实记录与最早星心 先取 $y\in\{H-3,H-6,\ldots,3\}$。固定目标 $v_y=(2,y)$，四个查询端点为 $$ e'_y=(0,y+2),\qquad e_y=(-4,y),\qquad f_y=(2,y),\qquad f'_y=(6,y+2). $$ 它们的根深度依次为 $$ \begin{aligned} \operatorname{depth}(e'_y)&=y+4, & \operatorname{depth}(e_y)&=2H+2-y,\\ \operatorname{depth}(f_y)&=2H+4-y, & \operatorname{depth}(f'_y)&=4H+6-y. \end{aligned} $$ 初始上行已经达到高度 $H+2$。首个内层早端达到 $H+5$；之后早端深度每轮加三，而本轮晚端只比早端深二。因此所有内层早、晚端都是全局高度记录。外层早端在初始上行中产生；外层晚端在最后继续正臂时产生，也是记录。发现顺序严格为 $$ e'_y