一类四邻接网格图森林的匹配问题：沿根叶路径计费¶

历史研究记录（2026-10-12 更新）。 一般三次方上界现已由独立证明解决。下文保留各阶段的推导、余项和反例；“尚未解决”指当时状态或该局部方法，更强的辅助命题不自动随一般上界成立。

本文分析候选列表程序，补充一般上界。道路树可以有任意分叉；下面的参数记录查询树或道路树的叶子数量。

结论与参数¶

令 \(T\) 为最后一次候选仍非空时的完整位移集合，以初始零位移为根。它是一棵可平移嵌入棋盘的诱导树。最后使候选全部失败的新位移不属于 \(T\)；直接越界清空后的位移也不计入。

记 \(L_T\) 为这棵有根树的叶子数，单点树取 \(L_T=1\)。对每个道路分量 \(C\)，记 \(\ell_C\) 为它的无根叶子数，单点分量取 \(\ell_C=1\)。设道路总格数为 \(N\)。

定理。 候选检查总数满足

\[ \boxed{W\le N+3(n-1)\sum_C|C|\min(L_T,\ell_C).} \]

因此，只要有效查询树的叶子数有常数上界，或者每个道路分量的叶子数有常数上界，就有 \(W=O(nN)\)，时间为 \(O(n^2+m+nN)\subseteq O(n^3+m)\)。如果 \(N=0\)，则直接有 \(W=0\)，无需定义 \(T\)。

两个具体推论：

查询的新位移沿一条路径从端点向前延伸时，\(L_T=1\)，故 \(W\le(3n-2)N\)，宿主道路可以任意分叉。
有效查询树是一条路径、从中间出发并向两端交错增长时，\(L_T\le2\)，故 \(W\le(6n-5)N\)。道路各分量均为路径时也有这个界，改进了此前的路径分量证明中的常数。

一般森林的两个叶子参数都可能很大，所以该定理还没有消去一般上界中的对数因子。

一条查询根叶链上的成功点¶

固定目标道路格 \(v\)。当非零新位移 \(p\) 首次出现、且起点 \(v-p\) 的整个当前前缀合法时，称它为一次命中 \(v\) 的成功。令 \(H(v)\) 为这种成功的总数。

先只取一条查询根叶路径上的成功位移，并补上初始零位移。沿这条路径的祖先顺序与首次访问顺序一致，即使实际行走在中途访问过其他分支。

取其中按顺序排列的四个不同点 \(a,b,c,d\)。

第一种禁止情形¶

若 \(a+d=b+c\)，则四点必须共线。

确实，第 \(b\)、\(d\) 个锚点各自成功时的副本中，从 \(a\) 到 \(b\)、从 \(c\) 到 \(d\) 的两条平移路径都有端点 \(v+a-b=v+c-d\) 和 \(v\)。道路森林中的路径唯一，所以这两段是平移关系。同理，从 \(a\) 到 \(c\) 与从 \(b\) 到 \(d\) 的路径也是平移关系。

这四段在查询树中组成一个闭合游走。令 \(u=b-a\)、\(w=c-a\)，用有向边 \(xy\) 的权值 \(\det(x,y)/2\) 求和，该闭合游走的权值为 \(\det(u,w)\)。树中的闭合游走对每条边正反经过次数相同，权值为零，所以四点共线。这与一般复杂度证明的面积论证相同；这里分别使用各锚点成功时已经存在的路径。

第二种禁止情形¶

等式 \(a+c=b+d\) 不可能成立，连共线情形也不例外。

否则 \(a-d=b-c\)。在 \(d\) 成功时，把查询链的外段从 \(a\) 到 \(d\) 平移到以 \(v\) 结尾；在 \(c\) 成功时，把内段从 \(b\) 到 \(c\) 同样平移。两条简单路径的端点完全相同，都是 \(v+a-d=v+b-c\) 和 \(v\)，因此道路森林中的唯一路径要求它们等长。

但四点沿同一查询链依次出现，外段严格包含内段，长度必然更大，矛盾。

所以，若这四点构成非退化平行四边形，唯一可能的对角和关系是 \(a+b=c+d\)：最早两点必须互为对角。

给水平距离加上访问方向¶

设上述成功点与零位移组成的点集为 \(S\)，其包围盒为 \(h\times w\)，其中 \(h,w\le n\)。

每个有 \(k\) 个点的非空行，从最左点连向其余各点，产生 \(k-1\) 个不同正水平距离。为每个距离再标记访问方向：左端先出现记为正，右端先出现记为负。

同一个“距离、访问方向”不能在不同行出现。 否则两行的两对端点构成非退化平行四边形。由于两对都先左后右，或都先右后左，最早两个端点不可能互为对角，违反上面的结论。

正距离至多有 \(w-1\) 种，每种只有两个访问方向；非空行至多有 \(h\) 个。因此

\[ |S|\le h+2(w-1)\le3n-2. \]

扣去补入的零位移，每条查询根叶链对固定目标格至多贡献 \(3n-3\) 次成功。交换横纵坐标，还可把点数界写为 \(\min(h+2w,2h+w)-2\)。

按查询叶子分组¶

将 \(T\) 的每个非根顶点分配给它的某个后代叶子。同一组的点都落在对应的根叶链上；每个成功位移只分配一次。对每组都补入零位移并应用上面的计数，得到

\[ H(v)\le3(n-1)L_T. \]

单点模板没有成功新位移；当 \(n=1\) 时，右侧也恰为零。

对偶：也可以只按道路叶子分组¶

将 \(v\) 所在道路分量以 \(v\) 为根，记其有根叶子数为 \(L_v\)。把原先每次成功对应的起点 \(a=v-p\) 分配给一条包含它的宿主根叶路径 \(R\)。

固定这样一条 \(R\)。交换两棵树的角色：把最终有效查询树 \(T\) 作为新宿主，把沿 \(R\) 从 \(v\) 向外行走作为新的单端路径查询。新查询在道路点 \(x\) 时的位移是 \(q=x-v\)。

对该组中任一原起点 \(a\)，令新起点为 \(p=v-a\)。当新查询走到 \(a\) 时，它的完整前缀平移后为

\[ R[v,a]-v+p=R[v,a]-a. \]

原先的成功说明：这正是原查询树内从 \(p\) 到零位移的路径，所以它全部包含在 \(T\) 中。新查询因此在位移 \(q=a-v\) 时成功命中零位移。这里把各事件按它们在 \(R\) 上的深度重新排列，不依赖原访问顺序。

\(T\) 可以整体平移进同样大小的棋盘，因此这是一个合法的新道路树实例。每组都适用已证明的单端路径界，故

\[ H(v)\le3(n-1)L_v, \qquad H(v)\le3(n-1)\min(L_T,L_v). \]

这一步分别按两棵树的叶子分组，无需将两个叶子数相乘。

总检查量¶

每个起点至多失败一次，因此失败检查总数至多为 \(N\)。成功检查按目标格求和，而分量 \(C\) 内每个根的有根叶子数都不超过 \(\ell_C\)。所以

\[ W\le N+\sum_{v\in F}H(v) \le N+3(n-1)\sum_C|C|\min(L_T,\ell_C). \]

最后清空列表的一轮没有成功检查，已经由失败项覆盖；直接越界清空也不会增加候选检查。重复访问旧位移只影响输入长度 \(m\)。由此得到开头的定理。

把短分枝的检查归到祖先点¶

叶子数很大时，还有一个补充上界。取 \(T\) 中包含根的连通子树 \(K\)，其有根叶子数为 \(b\)。对每个点 \(p\)，令 \(\pi(p)\) 是根到 \(p\) 的路径上最后一个属于 \(K\) 的点。设

\[ \mu=\max_{q\in K}|\{p\in T:\pi(p)=q\}|. \]

则

\[ \boxed{W\le\mu[1+3(n-1)b]N.} \]

证明。 把每个成功检查记为一对 \((a,p)\)，并加入全部 \(N\) 个初始合法配对 \((a,0)\)。若成功检查数为 \(S\)，这个集合的大小就是 \(N+S\)。由于失败检查至多为 \(N\)，有 \(W\le N+S\)。

把 \((a,p)\) 映到 \((a,\pi(p))\)。若 \(\pi(p)=p\)，配对不变；否则连通查询前缀必先访问这个真祖先。因此映射后的配对也合法，且发生时间不晚于原配对。每个配对至多有 \(\mu\) 个原像。所以，若落在 \(K\) 上的非零成功检查共有 \(S_K\) 次，则

\[ N+S\le\mu(N+S_K). \]

把 \(K\) 的点按其 \(b\) 条根叶链分配，沿用前文的链计数，得到 \(S_K\le3(n-1)bN\)，即得结论。这里仍使用原始查询的完整前缀，没有把它改成只访问 \(K\) 的查询。

如果每个点到其祖先投影的树距离至多为非负整数 \(r\)，则同一个 \(q\) 的所有原像都在以它为中心、曼哈顿半径为 \(r\) 的菱形内，故

\[ \mu\le B_r=2r^2+2r+1,\qquad W\le B_r[1+3(n-1)b]N. \]

这允许 \(T\) 有很多叶子，只要一棵根叶路径数较少的子树之外，各分枝都足够短。

宿主主路径旁的分枝有界¶

假设每个道路分量都有一条路径 \(R\)，该分量的每个点到 \(R\) 的树距离至多为 \(r\)。那么任意查询都有

\[ \boxed{W\le(2r^2+2r+1)(6n-5)N.} \]

只需证明有效查询树存在上节所需的子树 \(K\)，且 \(b\le2\)、距离仍不超过 \(r\)。取最终有效查询树的一个合法嵌入，记其根为 \(z\)，嵌入后的子树为 \(Q\)。

若 \(Q\) 与宿主主路径 \(R\) 相交，交集是一段路径。取这段路径及从 \(z\) 到它的连接作为 \(K\)。以 \(z\) 为根时，\(K\) 至多有两个叶子。对每个查询点 \(p\)，它在 \(K\) 上的最后一个根路径祖先位于它通往 \(R\) 的路径上，所以剩余距离不超过 \(r\)。
若 \(Q\) 与 \(R\) 不交，则它位于同一条挂枝中。令 \(s\) 为 \(Q\) 内离 \(R\) 最近的点，取 \(K\) 为从 \(z\) 到 \(s\) 的路径。所有点通往 \(R\) 的路径都经过 \(s\)，上述距离界仍成立，此时 \(K\) 只有一个有根叶子。

于是可直接使用 \(b\le2\) 的投影上界，无需把距离放宽到两倍。单点分量、单点查询和 \(r=0\) 都包含在内。

当 \(r\) 为常数时，这给出 \(O(n^2+m+nN)\) 时间。该范围超过有界叶子数的情况：一条长蛇形主路径可以挂上 \(\Theta(n^2)\) 个单格叶子，同时仍取 \(r=1\)。一般分枝深度可能很大，这个补充界仍未证明一般森林的三次方上界。

任意查询中的重复水平标记共享一个完整前缀¶

回到固定目标 \(v\) 的全部成功位移，不再限制它们属于一条查询根链。补入初始零位移；每行仍从最左点向其余点作距离标记，并保留较左端点是否先访问的信息。同一种标记在同一行至多出现一次，但现在可以跨行重复。

把一组相同标记的两端按访问时间写为 \((e_i,f_i)\)，前者较早。于是存在一个固定的非零水平向量 \(\delta\)，满足

\[ f_i-e_i=\delta. \]

嵌套引理。 这些标记的时间区间两两严格包含。确实，假设一组的较早端点先出现。如果两个区间分离或交错，则由

\[ e_i+f_j=f_i+e_j \]

可知，按时间排列的四点满足最早与最晚之和等于另两点之和。两条标记位于不同行，所以平行四边形非退化，违反前文第一种一般时间禁形。唯一可能的顺序是

\[ \operatorname{time}(e_i)<\operatorname{time}(e_j) <\operatorname{time}(f_j)<\operatorname{time}(f_i). \]

因此，取刚访问完这组全部较早端点时的真实完整查询前缀 \(P\)，它包含所有较早端点，还不包含任何较晚端点。每个较晚成功候选在这一阶段已经匹配整个前缀，并且

\[ a_i=v-f_i,\qquad a_i+e_i=v-\delta. \]

所以这组较早端点是同一个完整前缀在同一个固定目标上的静态成功锚点。可以使用一般证明的完整前缀限制；不过，不同距离对应的共同切分前缀可能不同，尚未由此得到总量计费。

此外，每条查询端点间路径在较晚成功副本中都被平移为同一条宿主路径，端点为 \(v-\delta\) 和 \(v\)。这些查询路径具有相同的方向词。它们未必边不交，不能直接按互不重复的分枝支付费用。

距离一有更强边界。两个相邻成功位移必是查询父子，父亲先出现。记父亲的根方向词为 \(w\)，父子方向为 \(\varepsilon\)，词长为 \(k\)。相应的两个宿主起点相邻，到固定目标的树距离相差一，因此唯一树路径要求

\[ w\varepsilon=\varepsilon w,\qquad w=\varepsilon^k. \]

所以这条查询边位于从根出发的初始直线射线上。水平距离一的标记只在根所在行出现，不能跨行重复。距离至少为二时，单个标记可以重复线性于方框边长的次数；目前仍缺少不同标记之间的全局费用分配。