# 一类四邻接网格图森林的匹配问题：跨前缀的重叠约束

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

本篇证明跨前缀的重叠约束、历史高重叠图的共线性，以及高重叠方向切换的总倍率预算。后半部分将实际检查次数归约到根路径匹配总量，并证明其中一些部分受控。完整总量界仍为猜想；这些结果尚未消去[一般上界](../../complexity.zh.md)中的对数因子。

**当前结论：无权前沿的线性总量界已被否定。** 末节给出同根诱导网格树族，其前沿数可达 $\Theta(nN)$，其中 $N=\Theta(n^2)$。这不反驳实际算法的三次方界，也没有反驳直接根路径匹配总量的目标；大量前沿不能同时满足真实完整前缀。下文保留有效归约与历史障碍，前沿线性猜想不再作为待证目标。

设道路集合为 $F$，其诱导四邻接图是森林，$N=|F|$，道路位于 $n\times n$ 方格内。所有平移只改变位置，不旋转或翻转。下面的点集连通性都指四邻接连通。

## 两个非平行部分平移的统一引理

取非空有限点集 $U\subseteq F$，以及非空连通集 $P,R\subseteq U$。若整点位移 $d,e$ 线性无关，且

$$
P+d\subseteq F,\qquad R+e\subseteq F,
$$

则

$$
\boxed{|(P+d)\cap U|+|(R+e)\cap U|\le |U|-1.}
$$

这里 $U$ 不必连通，两份平移的域不必嵌套，四份连通副本也不必位于同一个道路分量。

### 第一步：在道路森林上定义面积势能

记 $\det(x,y)=x_1y_2-x_2y_1$。在每个道路分量中选一个根，沿唯一根路径累加边权，得到函数 $\Phi$，使每条有向道路边满足

$$
\Phi(y)-\Phi(x)=\det(x,y).
$$

各分量的根值可以独立任取。对 $x\in P$ 定义

$$
f_d(x)=\Phi(x+d)-\Phi(x)-\det(d,x).
$$

若 $x,y$ 在 $P$ 中相邻，则原边和平移后的边都是道路边，因而

$$
f_d(y)-f_d(x)
=\det(x+d,y+d)-\det(x,y)-\det(d,y-x)=0.
$$

由连通性，$f_d$ 在 $P$ 上为常数，记为 $c_d$。同理得到在 $R$ 上的常数 $c_e$。于是每个 $x\in P$ 都满足

$$
\Phi(x+d)-\Phi(x)=-\det(x,x+d)+c_d.
$$

这条恒等式不要求两端是相邻道路格。

### 第二步：辅助图不能有环

在顶点集 $U$ 上建立辅助无向图：

- 若 $x\in P$ 且 $x+d\in U$，加入边 $x(x+d)$。
- 若 $x\in R$ 且 $x+e\in U$，加入边 $x(x+e)$。

两类边无自环、无重边，边数就是引理左侧。假设存在一个简单环。环上所有点属于某个仿射格

$$
x_0+\mathbb Z d+\mathbb Z e.
$$

以 $d,e$ 为坐标基底后，每条边成为整数方格的一条单位边。不同单位边只能在共同端点相交，所以简单环围成一个面积非零的简单多边形。变换回原坐标后仍有

$$
\sum_{xy\text{ on the cycle}}\det(x,y)\ne0.
$$

沿环走正向平移边时，势能增量为 $-\det(x,y)+c_d$；反向时为 $-\det(x,y)-c_d$。另一类边同理。闭环的总位移为零，而 $d,e$ 线性无关，因此每类平移的正反次数分别相等，常数项全部抵消。势能沿环求和也为零，故

$$
0=-\sum_{xy\text{ on the cycle}}\det(x,y),
$$

矛盾。辅助图是森林，边数至多为 $|U|-1$，引理得证。

这一论证只适用于两种非平行平移。不能直接把任意多个方向的边合并后仍视为森林。

## 旧候选删除后的约束

设 $P\subseteq Q$ 是非空连通集，且 $P,P+d,Q,Q+e$ 都在道路森林中，$d,e$ 非平行。定义

$$
I_d(P)=|P\cap(P+d)|.
$$

在统一引理中取 $U=Q$、$R=Q$，得到

$$
\boxed{|(P+d)\cap Q|+I_e(Q)\le |Q|-1.}
$$

特别地，$I_d(P)+I_e(Q)\le |Q|-1$。这里没有要求 $Q+d\subseteq F$，所以旧平移对应的候选可以已经被删除。

若 $k>1$ 且 $I_e(Q)\ge(1-1/k)|Q|$，则

$$
|Q|\ge k\bigl(|(P+d)\cap Q|+1\bigr)
\ge k\bigl(I_d(P)+1\bigr).
$$

旧副本一旦全部包含于新基准中，中间的交集项就等于 $|P|$。因此旧证书不会仅因候选删除而失效，但要使用它，仍需保留同一个合法基准副本。

另取 $U=F$，可得一个不要求域嵌套的大小约束：

$$
\boxed{|P|+|R|\le N-1.}
$$

在算法中固定一个最后有效前缀的幸存起点为基准，记其他起点相对它的位移为 $d$，成功匹配的完整前缀大小为 $\ell(d)$，包括初始零位移。对非平行位移有

$$
\ell(d)+\ell(e)\le N-1.
$$

因此寿命大于 $(N-1)/2$ 的起点都与基准共线，连同基准至多有 $n$ 个。这只是寿命的成对约束，尚未控制全部寿命之和。

## 一个倍率区间内的全部历史高重叠边

取 $1/2<\alpha<1$，令 $\rho=\alpha/(1-\alpha)$，固定 $s\ge1$。建立一个历史图：顶点是所有初始候选；当某个完整查询前缀的大小为 $j\in[s,\rho s)$，两个仍合法的副本重叠至少 $\alpha j$ 个点时，在相应起点之间加入边。加入的边永久保留，即使候选后来被删。

**结论：这个图的每个非平凡连通分量都位于一条直线上，至多包含 $n$ 个起点。**

只需证明共享一个起点的两条边平行。将两条边按出现时刻排序，把公共起点的两份前缀记为 $P\subseteq Q$，另两个起点相对它的位移记为 $d,e$。公共起点在较晚时刻仍合法，所以两份基准都可用；旧的另一个起点可以已经删除。

若 $d,e$ 非平行，由上节有

$$
\alpha|P|+\alpha|Q|
\le I_d(P)+I_e(Q)\le |Q|-1.
$$

于是

$$
|Q|\ge\frac{\alpha|P|+1}{1-\alpha}
>\rho|P|\ge\rho s,
$$

与区间定义矛盾。沿图路径连续应用这个结论，整个分量共线。方格内任一直线至多包含 $n$ 个整点，得到规模界。

例如取 $\alpha=2/3$，就能在每个 $[s,2s)$ 区间内保留全部历史高重叠边。不能把所有倍率区间直接合并；跨多个尺度后，历史图确实可能出现非共线的环。

这仍没有证明总时间为三次方。剩余问题包括轻重叠副本如何计费，以及不同区间能否共用同一份费用。

## 高倍率方向段的最大倍率之和小于三倍边长

上一节固定重叠阈值。下面可以把不同阈值、不同尺度合并计费，但仍只计高重叠证书，尚未覆盖全部成功检查。

设非空容器按时间嵌套为 $Q_i\subseteq F$。每张证书包含非空连通域 $D_i\subseteq Q_i$ 和非零整点位移 $d_i$，满足 $D_i+d_i\subseteq F$。定义

$$
j_i=|Q_i|,\qquad J_i=|(D_i+d_i)\cap Q_i|,\qquad
\kappa_i=\frac{j_i}{j_i-J_i}.
$$

域可以随证书变化，不要求它们互相嵌套。容器也不必连通。

在容器内，仅对 $x\in D_i$ 且 $x+d_i\in Q_i$ 加入边 $x(x+d_i)$。辅助图由互不相交的直线链组成，边数为 $J_i$。每条链至多有 $n$ 个格点，所以

$$
1\le\kappa_i\le n.
$$

若较早与较晚证书的位移非平行，由统一引理及容器单调性，得到

$$
J_i+J_k
\le |(D_i+d_i)\cap Q_k|+|(D_k+d_k)\cap Q_k|
\le j_k-1\qquad(i<k).
$$

在每个时刻只保留 $\kappa_i\ge4$ 的证书。同一时刻的这些证书必定平行，否则两项重叠都至少为容器大小的四分之三，违反统一引理。按时间合并连续同方向的证书；正反平移视为同一方向，没有高倍率证书的时刻跳过。每个方向段只选取达到该段最大倍率的一张证书，并按时间重新编号为 $1,\ldots,r$。

**结论：这些代表证书满足**

$$
\boxed{\sum_{i=1}^{r}\kappa_i<3n.}
$$

当没有证书或只有一个方向段时结论直接成立。以下设至少有两个方向段，因而 $n\ge4$。相邻代表的位移非平行，于是

$$
\frac{j_{i+1}}{\kappa_{i+1}}\ge J_i+1
=\left(1-\frac1{\kappa_i}\right)j_i+1,
\qquad
j_{i+1}>\frac34\kappa_{i+1}j_i.
$$

取自然对数并求和：

$$
\sum_{i=2}^{r}\log(3\kappa_i/4)<\log(j_r/j_1).
$$

函数 $x/\log(3x/4)$ 在 $x\ge4$ 上递增，因为导数的符号由 $\log(3x/4)-1>0$ 决定。结合 $\kappa_i\le n$、$j_1\ge\kappa_1\ge4$ 及 $j_r\le n^2$，得到

$$
\sum_{i=2}^{r}\kappa_i
<\frac{n}{\log(3n/4)}\log(j_r/j_1)
\le\frac{n\log(n^2/4)}{\log(3n/4)}<2n.
$$

最后一步用到 $n^2/4<(3n/4)^2$。再加上 $\kappa_1\le n$ 即得所需预算。

在真实查询中，固定最后有效前缀的一个幸存起点作为基准，只考察截至该前缀的证书，以基准起点的当前完整前缀作为容器。一个候选被删除后，取它最后成功匹配的旧前缀作为域，仍可继续提供证书；随后容器增大还可能吸收更多旧副本的点。因此上述定理包含候选被删除后的历史信息。最后全部清空时的失败检查仍计入原有的至多 $N$ 次失败预算。

该定理只控制每个方向段的最大倍率之和。目前没有证明所有检查都能收费到这些方向段；大量轻重叠副本的费用仍需另行处理。同一方向的多个不连通域也不能直接合并成一个证书，因为统一引理要求每张证书的域连通。

## 将总检查次数归约为根路径匹配总量

下面的归约是严格结论，但归约后的线性总量界仍是猜想。

道路非空时，取最后一个仍有候选存活的完整查询树 $T$，包含初始零位移；最终使全部候选失败的新位移不在其中。可以取 $Q=T$，也可以选它的一个幸存起点 $a_*$，令 $Q=C-a_*$，其中 $C$ 是包含该起点的整个道路分量。两种选择都得到包含 $T$ 的、以零位移为根的诱导树。

对每个初始起点 $a\in F$，定义

$$
K_a=\operatorname{comp}_0\bigl(Q\cap(F-a)\bigr),
\qquad S(Q,F)=\sum_{a\in F}|K_a|.
$$

这里取交集诱导图中包含零位移的连通分量。等价地，$p\in K_a$ 当且仅当查询树中从零到 $p$ 的整条路径平移到 $a$ 后都在道路上。

若 $C_a$ 是起点所在的道路分量，也可写成 $K_a=\operatorname{comp}_0(Q\cap(C_a-a))$。求和仍包含参考分量之外的所有起点。

每次真实成功检查的新位移都属于相应的 $K_a$，且同一起点不会重复检查该位移。因此该起点成功至多 $|K_a|-1$ 次。每个起点至多失败一次，总失败数至多为 $N$，从而

$$
\boxed{W\le N+\sum_{a\in F}(|K_a|-1)=S(Q,F).}
$$

道路为空时直接有 $W=0$。重复位移与直接越界清空均不增加这个检查数。

**待证猜想。** 是否存在绝对常数 $c$，使所有上述实例满足

$$
S(Q,F)\le c nN\,?
$$

若能证明，即得时间 $O(n^2+m+nN)\subseteq O(n^3+m)$。不必对每个目标格分别证明线性命中界；这个总量问题允许少数目标有很多根路径匹配。即使只证明上述 $Q=C-a_*$ 的特例，也足以完成算法的上界。

常数一已经不成立。取整数 $s\ge1$、$n=4s+1$，道路是一条完整底边主干及所有偶数列的全高竖齿，参考根为中央齿的中点；取整个分量作为 $Q$。逐条竖线和同高梳子计数可得

$$
N=8s^2+8s+1,\qquad
S(Q,F)=36s^3+34s^2+12s+1.
$$

因此 $S(Q,F)/(nN)\to9/8$。这个族没有否定绝对常数上界，也没有构成运行时间的超三次方反例。

上述精确式可以逐组核对。用坐标 $0,\ldots,4s$，主干在高度零。偶数列上高度 $y\ne2s$ 的起点只匹配一段竖线，大小为 $2s+1+\min(y,4s-y)$。对同高起点 $(2i,2s)$，令 $t=\min(i,2s-i)$；公共主干有 $2s+1+2t$ 个点，并有 $s+1+t$ 根各贡献 $4s$ 个额外点的完整齿。奇数列主干起点只匹配根本身。对这些大小求和便得到多项式。

## 祖先起点的一部分总量已经受控

给每个道路分量任意定根。在根路径匹配配对中，记道路终点为 $b=a+p$。只统计 $a$ 是 $b$ 的祖先的配对，允许二者相等，则总数至多为

$$
(3n-2)N.
$$

固定终点 $b$，将道路根到它的路径逆序，作为一个新的单端路径查询，以 $Q$ 为新的道路树、零点为固定目标。每个原合法祖先起点 $a$ 对应新查询位移 $a-b$，以及新起点 $b-a$。新查询的整个前缀平移到该起点后，恰好是 $Q$ 中从该点回到根的路径，所以这是真正的完整前缀成功。

由[根叶链定理](complexity-chains.zh.md)，每个终点至多对应 $3n-3$ 次非空成功，加上空词共 $3n-2$ 次。对终点求和得到结论。原来的 $Q$ 不必能完整嵌入宿主，也无需限制道路分量数。

这部分覆盖顺着宿主根方向向下的匹配。纯上行、或先上行再下行的路径仍未合并计费，因此一般总量猜想仍然开放。

## 固定终点的匹配端点只有初始直线段能相邻

固定宿主终点 $b$，令

$$
A_b=\{q\in Q:\text{the root path to }q\text{ matches a road path ending at }b\}.
$$

若查询父子 $q,q+\delta$ 都属于 $A_b$，其中 $\delta$ 是单位方向，则从根到 $q$ 的方向词只能由 $\delta$ 重复组成。

证明如下。记该方向词为 $w_q$，其长度为 $k$。两次匹配的起点是

$$
a=b-q,\qquad a'=b-q-\delta=a-\delta.
$$

二者为相邻道路格。宿主是诱导森林，所以它们之间有道路边，且到 $b$ 的唯一路径长度分别为 $k$ 和 $k+1$。因此从 $a'$ 到 $b$ 必先沿 $\delta$ 到达 $a$，再走原路径。这条路径的方向词同时为

$$
\delta w_q=w_q\delta.
$$

逐字比较得 $w_q=\delta^k$，引理得证。

如果初始射线端点 $k\delta$ 能匹配到 $b$，则同射线上更短的端点也能匹配到 $b$，只需截取对应宿主路径的后缀。所以查询诱导子图 $Q[A_b]$ 由包含根的四向直线段和其余孤立点组成；其他孤立点的根路径至少转过一次方向。

四向直线段在方格内至多有 $2n-1$ 个点。因此全部直线根路径匹配总数至多为

$$
(2n-1)N.
$$

这个结论没有控制非直线根路径的孤立端点总量，不能仅由诱导子图很稀疏就推出完整总量界。

## 纯上行匹配的查询前沿归约

在宿主的每个分量中选定根。对每个终点 $b$，令 $U_b\subseteq Q$ 为所有纯上行匹配的查询端点，即查询根路径平移后从起点到 $b$ 始终沿宿主父指针前进；包含长度为零的路径。

在查询祖先序中，令 $M_b^Q$ 为 $U_b$ 内没有更深匹配后代的极大点。将每个匹配端点分配给一个极大后代。每组位于同一条查询根链上；把这条链作为完整单端查询运行，组内匹配都是对固定目标 $b$ 的合法命中。由根叶链定理，每组含空词至多有 $3n-2$ 个匹配。于是严格有

$$
S_{\mathrm{up}}(Q,F)=\sum_{b\in F}|U_b|
\le(3n-2)\sum_{b\in F}|M_b^Q|.
$$

**这个充分条件后来已被否定。** 曾希望证明 $\sum_b|M_b^Q|=O(N+|Q|)$，或只证明 $O(n^2)$，以控制纯上行部分。末节的参数构造同时否定这两个界，即使查询与宿主相同且同根也如此。上面的归约不等式仍然成立，但不能继续用无权前沿数完成总量证明。一般根路径总量还包含先上行再下行的匹配。

## 同根完整参考树：可比部分的前沿至多为道路点数

下面只考虑一棵道路树，令查询树与宿主树相同，二者取同一个根 $r$。记道路点数为 $N$。一个纯上行前沿事件由宿主起点 $a$、终点 $b$ 和查询端点 $q\in M_b^Q$ 组成，满足

$$
b=a+q-r,\qquad
\operatorname{depth}(a)=\operatorname{depth}(b)+\operatorname{depth}(q).
$$

按查询端点是否为宿主起点的祖先，将事件分为可比类和不可比类。深度等式排除了查询端点是起点的严格后代，故这两类覆盖全部事件。

**引理。** 可比类中，查询端点一定是宿主终点的祖先；当 $q\ne r$ 时，它还是严格祖先。因此可比类前沿总数满足

$$
E_{\mathrm{comp}}\le N.
$$

证明：空查询路径的结论直接成立。对于非空路径，令查询根词为 $u$，长度为 $k$；宿主起点的根词为 $W$，长度为 $h$。祖先条件说明它以 $u$ 开头，而纯上行匹配说明它以逆词 $u^{-1}$ 结尾。

树上简单路径的方向词没有相邻互逆字母。这两个逆向端段不能相接或重叠：若 $2k\ge h$，偶数长度的中心两字母互逆，或奇数长度的中心字母等于自身的逆，都与方向词约简矛盾。因此

$$
2k<h,\qquad \operatorname{depth}(b)=h-k>k=\operatorname{depth}(q).
$$

两点都是起点的祖先，故查询端点是终点的严格祖先。固定终点后，所有可比类查询端点都在根到该终点的一条链上；而查询前沿为反链，所以至多留下一个。对终点求和即得引理。

不可比部分不能一般地线性计费，末节给出了反例。这条可比部分引理仍然成立，但既不控制整个前沿，也没有处理不同宿主分量或不同根的情形。

## 满梳的前沿比值趋于二：历史下界

取偶数 $m\ge2$ 和整数 $H\ge1$。用行、列坐标表示一棵满梳：

$$
F=\{(0,c):0\le c\le2m\}
\cup\{(y,2i):1\le y\le H,\ 0\le i\le m\}.
$$

主干连接所有竖齿，相邻竖齿之间隔一列，所以它是诱导树。查询与宿主都取这棵树，共同根是中央竖齿远端 $r=(H,m)$，并且

$$
N=(m+1)H+2m+1.
$$

逐类计数查询前沿：

- 非中央竖齿的正高度终点，宿主纯上行只能向主干移动；它匹配查询初始竖链，只有一个极大端点。
- 主干上除中心外的终点，只能由主干一侧上行到达；匹配端点位于查询初始竖链和一侧主干组成的链上，所以前沿为一个。
- 主干中心可以由两侧上行到达，两个极大端点分别位于查询主干的两端，前沿为二。
- 中央竖齿上的正高度终点 $(y,m)$，对每根非中央查询齿的列 $c$，都有一个极大端点 $(y,c)$。其宿主起点为镜像齿端 $(H,2m-c)$，先到主干，再到中央列，最后沿中央齿朝根移动。这些端点恰好覆盖全部非空匹配的极大点，所以前沿为 $m$。

中央竖齿有 $H$ 个正高度终点，其他终点通常贡献一，主干中心额外贡献一。故

$$
E=\sum_b|M_b^Q|=(N-H)+1+mH=2mH+2m+2.
$$

特别地，取 $H=2m$，方框边长为 $n=2m+1$，得到

$$
N=2m^2+4m+1,\qquad
E=4m^2+2m+2,\qquad
\frac EN=2-\frac{6m}{2m^2+4m+1}\longrightarrow2.
$$

因此这个满梳本身已说明，一般界 $E\le CN+o(N)$ 若成立必须有 $C\ge2$。末节的新构造进一步排除了任何这样的绝对常数。这个满梳族只有线性于方框边长的分叉点，实际算法已由[长分枝证明](complexity-branches.zh.md)覆盖；前沿构造不是超三次方运行时间反例。

## 同根前沿可以限制到任意连通子树

继续令道路树同时作为查询与宿主，以 $r$ 为共同根。记前沿总数为 $E(F,r)$。取非空连通子树 $K$，令 $c$ 为其中原根深度最小的点。由树路径唯一性，它是子树中每个点的祖先。

只统计原实例中三个端点 $a,b,q$ 都属于子树的前沿事件，记为 $E_F[K]$。将这棵子树同时作为新的查询与宿主、改用其最浅点为共同根，则

$$
\boxed{E_F[K]\le E(K,c).}
$$

**证明。** 令原根到新根的方向词为 $u$，新根到查询端点的方向词为 $v$。原匹配的完整方向词是 $uv$，宿主从起点到终点也沿父指针读取这个词。由于两个宿主端点都在连通子树内，整条宿主路径都在其中。读完前缀后，所在点为

$$
a'=a+c-r\in K.
$$

剩余词从新起点走到原终点，恰等于新查询根路径；子树内的父方向也没有变化。因此它是新实例的纯上行匹配，并且

$$
b=a'+q-c.
$$

这一步允许任一个词为空。新起点可能不同于旧起点，旧非空查询也可能变成空查询。

旧查询端点未必仍是新前沿，因为截去公共前缀后可能出现更多匹配。不过，固定终点时，保留下来的旧前沿端点在子树中仍是反链。每个这样的点都有一个新极大匹配后代；两个不同旧点不可能选中同一个后代，否则它们同为该点的祖先而变得可比。因此可单射到新前沿。对终点求和即得结论。

## 与线性前沿界等价的内部路径收费

对每个前沿事件 $e=(a,b,q)$，令

$$
S_e=\operatorname{hull}_F\{a,b,q\}
$$

为连接三个端点的最小连通子树，包含全部必需的路径内部点。固定正整数 $C$。在所有同根完整参考树实例上，下列两个命题等价：

1. 前沿总数满足 $E(F,r)\le C|F|$。
2. 每个事件可以分配给其连接子树内的一个顶点，每个道路顶点至多接收 $C$ 个事件。

分配命题显然蕴含总量界。反过来，假设总量界对所有实例成立。任取资源点集 $U\subseteq F$，把它的诱导子图分成连通分量 $K_i$，各自最浅点为 $c_i$。事件的连接子树全部位于资源集内，当且仅当三个端点都属于其中同一个分量。由上一节的局部化引理，

$$
\#\{e:S_e\subseteq U\}
=\sum_i E_F[K_i]
\le\sum_i E(K_i,c_i)
\le C\sum_i|K_i|
=C|U|.
$$

把每个道路点拆为容量个资源槽。对于任意一组事件，取其全部可用资源点的并集；上式保证可用槽数不少于事件数。由 Hall 匹配定理，存在所需分配。

这给出了一个与一般线性界等价的收费目标，没有证明该界。只允许三个端点本身收费会施加更强条件，即使每点容量为二也已有合法反例。连接子树还不能缩写成起点到查询端点的一条路径，因为宿主终点未必位于该路径上。

## 先支付直线匹配，再统计非直线前沿

令 $E_{\mathrm{ns}}$ 只统计查询根路径至少转过一次方向的前沿事件，空路径归入直线类。非直线查询点的任何后代仍为非直线。因此每个非直线匹配都可以分配给一个非直线极大匹配后代。每组位于一条查询根链上，且不含空路径，由根链界至多有 $3n-3$ 个匹配。结合已证的全部直线匹配界，得到

$$
\boxed{S_{\mathrm{up}}(Q,F)\le(2n-1)N+3(n-1)E_{\mathrm{ns}}.}
$$

这适用于前文的一般纯上行模型，并不要求查询与宿主相同或同根。它把尚待控制的量缩小到非直线前沿，但没有证明这个量线性。

同根满梳族中，中央齿正高度终点贡献 $mH$ 个非直线前沿，主干贡献另外 $2m$ 个，因此

$$
E_{\mathrm{ns}}=mH+2m.
$$

然而一般的 $E_{\mathrm{ns}}\le N$ 已不成立：存在六十点诱导树，查询与宿主同根且完全相同，有六十三个非直线前沿，总前沿为八十九。这个有限反例仅排除常数一；末节的参数族进一步否定了任何常数下的非直线前沿线性界。

## 固定起点的终止匹配至多支付一个前沿

固定宿主起点 $a$，沿父指针读取的方向序列唯一。它在查询树中能读取的根路径构成一条链的初始段，记最深匹配端点为 $q_a$。称查询端点恰为这个最深点的前沿事件为终止前沿。每个起点至多对应一个，所以

$$
E_{\mathrm{term}}\le N.
$$

如果查询端点是真正的查询叶子，则不能继续，必为终止匹配。因此以查询叶子为端点的前沿也至多有 $N$ 个。这里没有把所有查询内部点的前沿一起计入这个界。

还有一个严格的传播限制。设前沿事件为 $(a,b,q)$，宿主下一步父方向为 $\delta$。若查询也能走到对应孩子，则匹配可以继续为

$$
b'=b+\delta,\qquad q'=q+\delta.
$$

如果新查询点在新目标处失去前沿地位，取一个严格更深的匹配后代 $s$。设到达它的最后一步方向为 $\varepsilon$。若 $\varepsilon=\delta$，去掉竞争匹配的最后一步，就在原目标处得到原查询点的严格匹配后代，违背原事件为前沿。因此

$$
\varepsilon\ne\delta.
$$

竞争匹配从另一孩子进入同一个新宿主目标。于是一次可继续匹配的前沿状态丢失，必发生在至少有两个孩子的宿主点。该结论指出了必须支付费用的位置，但尚未限制同一分叉点被多少个事件使用。

新前沿也有对偶限制。考虑一个非空新前沿，其前驱查询点为 $q$，新查询点为孩子 $q'$，旧、新宿主目标分别为 $b,b'$。去掉最后一步保证前驱本身是匹配。若它以前不是前沿，取旧前沿中严格支配它的点 $s$。假如这个竞争者也能按同一方向继续，那么它必须在另一查询孩子分支；否则其后继仍会严格支配新查询点。因此一次非空前沿的出现，要么涉及查询分叉，要么有旧竞争前沿在此终止。

特别地，当查询前驱只有一个孩子时，所有旧前沿支配者都必须终止。为新事件任选一个这样的终止前沿收费，所得分配自动是单射：固定旧终止事件后，旧宿主目标固定，新目标也是其唯一父亲；所有可能的新查询点都是同一个旧竞争查询点的祖先，却同时位于新目标的前沿反链中，所以至多有一个。于是

$$
E_{\mathrm{birth},1}\le E_{\mathrm{term}}\le N,
$$

其中左端只计从非前沿变成前沿、查询前驱恰有一个孩子的非空事件。空查询词没有前驱，应另计至多一个每宿主起点。查询分叉处的出现和宿主分叉处的消失仍需要一般的几何计费。

## 完整历史前缀的方向预算不能单独支付扫描量

前文的方向预算定理仍然成立，但下面的合法输入族排除了一个直接接法：不能仅把以真实完整前缀为容器的高倍率方向预算乘以道路点数，就支付全部扫描。

取奇素数 $p\ge3$，定义

$$
D=4p^2,\qquad
B_i=2(2pi+(i^2\bmod p)),\quad 0\le i<p.
$$

这些偶数行严格递增，均小于 $D$，每个非零有向差只出现一次。证明：差相等时，余数之差的绝对值小于 $2p$，先推出指标之差相等。模素数后得到指标之和相等，再利用二可逆，推出有序指标对相同。

查询根为零点。查询树由高度区间 $[0,4D]$ 的竖干、各行 $B_i$ 上长二的左齿，以及各偶数行 $[2D,4D]$ 上长四的右齿组成。先按高度递增完成所有左齿，走到竖干顶端，再按高度递减完成全部右齿，最后返回根。

宿主取两根竖干及其齿：

- 左竖干为 $x=-4$、$-4D\le y\le2D$；其负偶数行向左伸二格，非负偶数行向右伸四格。
- 右竖干为 $x=0$、$-4D\le y\le0$；其负偶数行向左伸二格。

负半平面两组齿之间有空列，只有零行横路连接两根竖干，所以宿主为诱导树。查询也是诱导树；每条边实际往返一次。准确参数为

$$
|P|=32p^2+2p+5,\qquad
N=88p^2+5,\qquad
n=24p^2+1,\qquad
m=64p^2+4p+8.
$$

起点 $(-4,-2D)$ 最后仍合法。零点上的成功查询位移，含初始根，恰为

$$
\{(0,y):0\le y\le4D,\ y\equiv0\pmod2\}
\cup
\{(4,y):2D\le y\le4D,\ y\equiv0\pmod2\}.
$$

竖干点的完整前缀落入宿主右梳，右齿端点的完整前缀落入宿主左梳。左齿点需要宿主正横坐标，奇数行需要不存在的奇行齿，右齿内部点需要不存在的完整竖干，因此没有其他命中。故

$$
H(0)=12p^2+1,\qquad
R_4=4p^2+1.
$$

第一项扣除了初始根，第二项为相同正水平距离四标记的重数。

### 全部实际前缀的倍率都至多为参数的一次方

对于真实完整前缀，定义

$$
I_d(P_j)=|(P_j+d)\cap P_j|,\qquad
\kappa_j(d)=\frac{|P_j|}{|P_j|-I_d(P_j)}.
$$

这里甚至允许在宿主中不合法的平移。对所有非零平移都有

$$
\kappa_j(d)\le25p.
$$

竖直方向的证明保留部分齿生成时刻。左齿行的差唯一性说明，任何非零竖移在负横坐标区域的交集至多有两个点。全部左齿完成后，损失至少为 $2p-2$，因此

$$
\kappa_j(d)\le\frac{32p^2+2p+5}{2p-2}\le25p.
$$

第一齿形成时竖移交集为空。完成一条左齿、尚未完成第二条时，损失至少为二，前缀至多有 $4p+6$ 点。若已完成 $t$ 条左齿，且 $2\le t\le p-1$，还允许下一齿出现一个点，则

$$
|P_j|\le4pt+2p+2t,\qquad
|P_j|-I_d(P_j)\ge2t-2,\qquad
\kappa_j(d)\le5p+2\le25p.
$$

非竖直方向还能得到 $\kappa_j(d)<4$。右齿出现之前只占三列，每条平移链至多三点，所以倍率至多为三。右齿阶段设已经生成的右侧点数为 $R$，包含部分齿。非竖干源点和竖干源点分别贡献至多竖干外点数与某一非零列点数，故

$$
0\le R\le4D+4,\qquad
|P_j|=4D+1+2p+R,\qquad
I_d(P_j)\le2p+R+D+1.
$$

于是

$$
4I_d(P_j)-3|P_j|\le2p-4D+5<0.
$$

更早的源域包含于当前完整前缀时，其交集也不会大于当前前缀的自交。因此上述界同时覆盖这类历史部分域证书。阈值至少四的方向段只有竖直方向，记其最大倍率和为 $B_{\mathrm{hist}}$，则

$$
B_{\mathrm{hist}}\le25p.
$$

### 实际扫描仍有二次于道路规模的费用

第 $k$ 条右齿位于 $4D-2k$，从零计数。所有偶数纵坐标起点

$$
(-4,t),\qquad -4D+2k\le t\le-2D
$$

都匹配该齿生成期间的完整前缀；共有 $D-k+1$ 个，每条齿产生四个新点。因此

$$
W\ge4\sum_{k=0}^{D}(D-k+1)
=2(D+1)(D+2)=\Omega(p^4).
$$

通用界同时给出 $W\le N(|P|-1)=O(p^4)$，所以

$$
W=\Theta(nN)=\Theta(p^4),
\qquad
N(1+B_{\mathrm{hist}})=O(p^3).
$$

这严格否定任何固定常数形式的 $W\le CN(1+B_{\mathrm{hist}})$；同一标记的重数也不能由真实完整历史前缀的最大倍率线性控制。限制在完整前缀容器很关键：这没有排除改用其他连通子模板、其他容器或额外几何费用的证明。该族只有线性于边长的道路点数，仍满足一般三次方目标。

把单棵宿主并排复制，还能排除加入棋盘基础费用后的同类建议。取

$$
F^\star=\bigcup_{j=0}^{p^2-1}\bigl(F+(8j,0)\bigr).
$$

每个副本宽七列，相邻副本之间有一列空格；总宽为 $8p^2-1$，高度仍为 $n$，所以整个森林仍放得进原方框。查询及真实移动序列保持相同。每个完整查询前缀连通，不可能跨过道路分量，因此候选计数严格逐分量相加：

$$
N^\star=p^2N=\Theta(p^4),\qquad
W^\star=p^2W=\Theta(p^6),\qquad
n^\star=n,\qquad m^\star=m.
$$

固定任一最终幸存参考，其完整前缀容器仍与原模板相同。其他分量的候选也受同一个自交上界约束，不能增加非竖直高倍率证书。因此

$$
B_{\mathrm{hist}}^\star\le25p,\qquad
(n^\star)^2+N^\star(1+B_{\mathrm{hist}}^\star)=O(p^5),
\qquad
W^\star=\Theta((n^\star)^3).
$$

故即使加入棋盘基础费用，固定常数倍的上述预算仍不足。这是对具体收费命题的渐近反例；这个合法森林族的实际复杂度与三次方目标相符。

## 前沿事件森林

前沿传播可以组织成一张完整的森林，而不仅是出现和消失的计数。这个结构适用于一般查询树和逐分量定根的宿主森林。

对每个可继续的前沿事件 $(a,b,q)$，令下一宿主点与查询孩子为 $b',q'$。如果后者仍为前沿，就连向这个继续事件。否则，任选新目标处严格支配它的前沿查询点 $p$，连向相应事件

$$
(a',b',p),\qquad a'=b'-p+r.
$$

其中 $r$ 是查询根坐标。终止前沿没有出边。

每条箭头都把宿主目标移到父亲，所以宿主深度严格减少；查询标签则移到严格后代。图没有有向环，且每个事件出度至多为一，因此其无向图是一片森林。每棵树恰有一个终止前沿作为根，树的数量至多为 $N$。

### 每棵事件树在宿主中投影为不重复的连通子树

固定一个宿主孩子及其父亲。该孩子处不同的旧前沿查询点不可比；各自选定的新前沿都是自己的后代。如果两个旧事件连向同一个新事件，那么两个旧查询点都会是同一个新查询点的祖先，产生矛盾。因此同一宿主孩子到父亲的前沿映射是单射。

从一棵事件树的根向下展开时，每个宿主孩子方向至多对应一个事件树孩子。不同宿主孩子的后代子树互不相交，所以整个投影不会发生重复。事件树的边恰映到宿主边，其像为连通子树 $K_\tau$，满足

$$
|\text{event tree }\tau|=|K_\tau|.
$$

沿事件箭头，查询标签始终移到严格后代。若终止根的查询标签为 $q_\tau$，则该事件树的所有查询标签都是它的祖先，位于同一条查询根链上。查询投影无需单射。

令全部终止前沿为 $\mathcal T$，得到精确分解

$$
\boxed{
E=\sum_{\tau\in\mathcal T}|K_\tau|,
\qquad |\mathcal T|\le N.
}
$$

不同事件树的宿主子树可以重叠。尚未控制的正是这些重叠的总量，不能把单棵树的投影单射当作整片森林的投影单射。

重叠还有一个限制：若两棵不同事件树的终止查询标签可比，包括相等，则它们的宿主投影必不相交。否则在公共宿主点处，两个前沿查询标签都位于同一条查询根链，却属于同一个前沿反链，只能为同一点；这会使同一个事件属于两个组件，产生矛盾。因此，对任意查询根链 $\Gamma$，

$$
\sum_{\substack{\tau\in\mathcal T\\q_\tau\in\Gamma}}|K_\tau|\le N.
$$

尚未支付的是终止查询标签不可比的组件之间的重叠。

### 真正发生替换的边

如果箭头源于前沿丢失，支配查询点严格深于原本的下一查询点。纯上行深度等式给出

$$
\operatorname{depth}(a')
=\operatorname{depth}(b')+\operatorname{depth}(p)
>
\operatorname{depth}(b')+\operatorname{depth}(q')
=\operatorname{depth}(a).
$$

由上一节的不同孩子结论，还有

$$
\operatorname{LCA}(a,a')=b'.
$$

普通继续箭头保持原起点不变。把同一起点下的连续前沿状态收缩为一段，仍得到森林；收缩后每条边都满足起点深度严格增加。

若连续段总数为 $R$，终止前沿数为 $T_{\mathrm{term}}$，可继续却丢失前沿的事件数为 $L_{\mathrm{loss}}$，则

$$
R=T_{\mathrm{term}}+L_{\mathrm{loss}}.
$$

这是段数的等式，不是全部前沿事件数的上界；段内长度仍需支付。以上结构没有证明一般线性前沿界。

## 同一组件中的同起点事件连续

固定一棵事件树及一个原宿主起点。它的全部纯上行终点都在该起点的宿主祖先链上。若同一组件有两个这样的事件，由宿主投影连通且单射，它们之间的事件路径恰好沿宿主祖先链向上。

普通继续不改变原起点；替换前沿则严格增加原起点的宿主深度。两端起点相同，所以中途不能发生替换。因此，同一组件中固定原起点的事件构成一段连续路径；同一起点的不同极大连续段必属于不同组件。不同组件的终止查询标签仍可能可比。

## 保根连通删除的前沿单调性

这里查询与宿主都是整棵树 $F$，共用根 $r$。记 $S_b(F,r)$ 为在宿主终点 $b$ 纯上行匹配的全部查询点，记其中查询祖先序下的极大点为 $M_b(F,r)$。包含空路径，所以每个终点至少有一个前沿。

若非空连通子树 $K\subseteq F$ 包含根，保留点的根路径和祖先关系都不变。对每个 $b\in K$，

$$
S_b(K,r)\subseteq S_b(F,r),\qquad
|M_b(K,r)|\le|M_b(F,r)|.
$$

第二个不等式需要极大点的单射，不能只声称旧极大点均保留。对每个新极大点，选取一个以它为祖先的旧极大点。新极大点互不可比，不可能选到同一个后代，因此得到单射。它已计入删除后新暴露的替补前沿。

对终点求和得到

$$
E(F,r)-E(K,r)\ge |F\setminus K|.
$$

### 自适应选择一条最大悬挂路径仍无常数费用

最大非根悬挂路径指：从非根叶沿度二点向内走，删掉首次遇到分叉或根之前的点，保留该分叉或根。即使可以挑选最便宜的一条，也不存在统一常数的每点前沿损失上界。

构造如下，坐标为 $(x,y)$。取整数 $g,H\ge2$、$L=H+2$，根为 $r=(0,0)$。用以下整数线段组成道路树：

- 左竖干：$x=-g$、$-H\le y\le H$。
- 右竖干：$x=g$、$-L\le y\le L$。
- 中央桥：$y=0$、$-g\le x\le g$。
- 左端横条：$y=\pm H$、$-2g\le x\le0$。
- 右端横条：$y=\pm L$、$0\le x\le2g$。

两竖干由中央桥连接，四个竖干端点各挂两条横臂。不同端横条错开两行，其他非连接部分相距至少两格，所以没有额外四邻接，图为诱导树。恰有八片非根叶，八条最大悬挂路径就是这些横臂，每条含 $g$ 个可删点。总点数与方框边长为

$$
N=4H+10g+5,\qquad n=\max(4g+1,2H+5).
$$

任删一臂 $P$，记保留端点为 $(x_s,y_s)$，令 $\sigma=\operatorname{sgn}(y_s)$。考虑保留的 $H$ 个宿主目标

$$
b_t=(x_s,y_s-\sigma t),\qquad 0\le t<H.
$$

它们都在中央桥外，其后代仅在通向相应末端的竖干和该末端两臂上。查询非空根路径先水平走；若转弯，其首段长度必须为 $g$。当 $t>0$ 时，能沿父边匹配到目标的非空根词只能从两个臂尖开始。当 $t=0$ 时，臂内其他起点只给同一水平查询链上的祖先。故旧前沿恰为两个不同根分支上的点

$$
M_{b_t}(F,r)=\{(-g,-\sigma t),(g,-\sigma t)\}.
$$

删除一臂恰好删除其中一个源点。两个查询点都处于 $|y|<H$，仍被保留；另一个臂尖仍提供匹配，且没有其他后代源点可以替补。因此这些目标的新前沿数都恰为一。其他保留目标由单调性不能净增加，再计入删除的目标，得到

$$
\boxed{E(F,r)-E(F\setminus P,r)\ge H+g.}
$$

这个结论同时适用于全部八条臂。固定 $g=2$，则每条可删路径的费用比都至少为 $1+H/2$，没有绝对常数上界。这否定了该自适应删枝归纳条件；它没有否定整体线性前沿界，也没有给出算法的超三次方反例。

## 两个事件组件可以共享任意多个分叉

宿主子树的交集必连通，但不一定是路径。下面给出一个合法参数族；它只否定交集形状的加强，不给出超线性前沿下界。

坐标为行、列，四个方向写作 $\mathrm N,\mathrm S,\mathrm E,\mathrm W$。取整数 $h\ge1$、根 $r=(-4,4)$，将以下四类完整格点路径取并，得到查询与宿主共同使用的树：

$$
\begin{array}{c|c}
\text{start}&\text{word}\\
(0,0)&\mathrm S^{4j}\mathrm W^2\mathrm S^2\mathrm W^4\quad(0\le j\le h)\\
(0,0)&\mathrm E^4\mathrm N^4\\
r&\mathrm N^2\mathrm E^2\mathrm N^{4h}\mathrm E^2\\
r&\mathrm E^4\mathrm N^2\mathrm E^2\mathrm N^{4h}\mathrm E^2
\end{array}
$$

第一类形成间隔四行的折齿。两条根查询分枝的长竖段相隔四列；除指定前缀和连接点外，各路径没有额外四邻接。因此图为诱导树，点数为

$$
N=20h+33.
$$

记 $U=\mathrm N^2\mathrm E^2$、$B=\mathrm E^4$。取两个查询叶及对应宿主起点：

$$
q_1^*=(-4h-6,8),\quad q_2^*=(-4h-6,12),\qquad
a_1^*=(4h+2,-2),\quad a_2^*=(4h+2,-6).
$$

这两个起点纯上行走到 $(0,2)$，分别读出查询叶的根词，形成两个终止事件。记其组件宿主投影为 $K_1,K_2$。它们同时包含子树

$$
\begin{aligned}
I_h={}&\{(y,0):0\le y\le4h\}\cup\{(0,1),(0,2)\}\\
&\cup\{(4j,-2),(4j,-1),(4j+1,-2):0\le j\le h\}.
\end{aligned}
$$

逐事件证书如下。表格给出第一个组件的查询词和原起点；第二个组件只需在查询词前加上 $B$，且把原起点向左移四格。

| 宿主目标 | 第一个查询词 | 第一个原起点 |
| --- | --- | --- |
| $(4j+1,-2)$ | $\mathrm N$ | $(4j+2,-2)$ |
| $(4j,-2)$ | $\mathrm N^2$ | $(4j+2,-2)$ |
| $(4j,-1)$ | $\mathrm N^2\mathrm E$ | $(4j+2,-2)$ |
| $(y,0)$，$0\le y\le4h$ | $U\mathrm N^{4h-y}$ | $(4h+2,-2)$ |
| $(0,s)$，$s=1,2$ | $U\mathrm N^{4h}\mathrm E^s$ | $(4h+2,-2)$ |

表中的查询点均为前沿。主干上再向查询链深处匹配，需要超出宿主最下折齿；折齿上再向深处匹配，其推定起点要么不是道路，要么首先向东纯上行，与该查询链的首方向不符。第二条查询链删去固定的首水平段后同理。

这些事件沿父边普通继续，只有 $(4j,-1)\to(4j,0)$、$j<h$ 发生替换：原下一查询词分别被其对应链上更深的前沿严格支配，支配者唯一。沿后续父边，所有事件均汇入相应指定终止事件。因此

$$
I_h\subseteq K_1\cap K_2,\qquad |I_h|=7h+6.
$$

这个共同子树在 $(4j,0)$、$0\le j<h$ 有 $h$ 个三度分叉。故两组件不仅可能共同转弯，还能共同经过任意多个分叉。终止查询标签不可比，与此前的不相交引理一致。

## 共享宿主祖先段需要互不相交的查询路径

设宿主点 $b$ 是 $c$ 的祖先，距离为 $\ell$，有 $k$ 个不同事件组件同时包含二者。每个组件的宿主投影连通且单射，所以其事件沿 $c$ 到 $b$ 的整段逐步向上连边。记第 $i$ 个组件在两端的查询标签为 $q_i(c),q_i(b)$。

每条事件箭头将查询标签移到严格后代，因此

$$
q_i(c)\preceq q_i(b),\qquad
\operatorname{depth}_Q(q_i(b))-\operatorname{depth}_Q(q_i(c))\ge\ell.
$$

所有 $q_i(c)$ 都是同一前沿反链 $M_c$ 中的不同点。它们的查询后代子树两两不交，故查询路径 $Q[q_i(c),q_i(b)]$ 两两点不相交。于是

$$
\boxed{
\sum_{i=1}^k
\bigl(\operatorname{depth}_Q(q_i(b))-\operatorname{depth}_Q(q_i(c))+1\bigr)
\le |Q|,
\qquad k(\ell+1)\le |Q|.
}
$$

允许 $b=c$、$\ell=0$，此时就是不同前沿点的计数。进一步，若 $k$ 个组件共同包含非空连通子树 $K$，从 $K$ 中最靠近宿主根的点到最远点的树距离为 $D$，则

$$
\boxed{k(D+1)\le |Q|.}
$$

这里 $D$ 是树距离，不是坐标高度。这个结论对任意合法的主导前沿选择规则都成立。

它只支付一个固定共同宿主段或共同子树的高度。不同宿主段得到的查询路径仍可能重复使用同一批查询点，不能直接对这些不等式求和；共享分叉的全部体积也尚未计入。因此，这个局部资源界没有推出总前沿量 $E=O(N)$。

## 任意多个组件可以共同经过任意多个分叉

前面的双组件族可以扩展为两个独立参数。仍使用行、列坐标，取整数 $k,h\ge1$ 和根 $r=(-4,4)$。查询与宿主共用下列完整路径的并：

$$
\begin{array}{c|c}
\text{start}&\text{word}\\
(0,0)&\mathrm S^{4j}\mathrm W^2\mathrm S^2\mathrm W^{4(k-1)}\quad(0\le j\le h)\\
(0,0)&\mathrm E^4\mathrm N^4\\
r&\mathrm E^{4i}\mathrm N^2\mathrm E^2\mathrm N^{4h}\mathrm E^2\quad(0\le i<k)
\end{array}
$$

宿主折齿间隔四行，查询长齿间隔四列；拐角间留有空格，除指定连接外没有额外四邻接。上下两部分通过第二条路径连接，所以仍为诱导树。三部分新增点数依次为 $(4h+1)+4k(h+1)$、$8$、$4(k-1)+k(4h+6)$，故

$$
N=8kh+4h+14k+5.
$$

包围盒高 $8h+9$、宽 $8k+3$。记 $U=\mathrm N^2\mathrm E^2$、$B_i=\mathrm E^{4i}$，选择查询叶及宿主起点

$$
q_i^*=(-4h-6,8+4i),\qquad
a_i^*=(4h+2,-2-4i),\qquad 0\le i<k.
$$

它们的纯上行路径都终止于 $b_*=(0,2)$，分别读出查询根词 $B_iU\mathrm N^{4h}\mathrm E^2$。查询点都是叶，因而给出 $k$ 个不同终止事件。记组件宿主投影为 $K_i$。

仍取此前定义的 $I_h$。对每个 $i$，共同子树上的证书为：

| 宿主目标 | 查询词 | 原起点 |
| --- | --- | --- |
| $(4j+1,-2)$ | $B_i\mathrm N$ | $(4j+2,-2-4i)$ |
| $(4j,-2)$ | $B_i\mathrm N^2$ | $(4j+2,-2-4i)$ |
| $(4j,-1)$ | $B_i\mathrm N^2\mathrm E$ | $(4j+2,-2-4i)$ |
| $(y,0)$，$0\le y\le4h$ | $B_iU\mathrm N^{4h-y}$ | $a_i^*$ |
| $(0,s)$，$s=1,2$ | $B_iU\mathrm N^{4h}\mathrm E^s$ | $a_i^*$ |

延长后的底横齿保证所有源点存在。每个查询齿仍是一条链；主干上的最大匹配深度由最下方折齿实现，折齿上的最大匹配由表中源点实现，再加深会要求不存在的源点或不符的首次方向。因此表中节点均为前沿。

只有 $(4j,-1)\to(4j,0)$、$j<h$ 发生替换：$B_iU$ 被同一查询齿上唯一的更深前沿 $B_iU\mathrm N^{4(h-j)}$ 支配。其他边普通继续，最终均到达指定终止事件。由此

$$
\boxed{
I_h\subseteq\bigcap_{i=0}^{k-1}K_i,
\qquad |I_h|=7h+6,
\qquad E\ge k(7h+6).
}
$$

共同子树仍有 $h$ 个三度分叉，因此组件共享次数和共享分叉数都没有绝对常数上界。不过，构造同时使用了 $\Theta(kh+k+h)$ 个道路点，没有给出超线性前沿下界。

这也展示了共享祖先段资源界的支付位置：取 $c=(4h+1,-2)$ 和 $b_*$，宿主距离为 $4h+5$。对应的 $k$ 条查询路径，是各查询齿从第一个北向节点到叶子的路径，每条恰有 $4h+6$ 个点，且彼此不交。共享长段由这些不同查询齿支付；跨不同宿主段的资源复用仍未解决。

## 一般线性前沿界不成立

取整数 $k,h\ge1$，用行、列坐标，根为 $(0,0)$。右梳由以下道路组成：

$$
\{(y,0):0\le y\le2k-2\}
\cup\{(2i,x):0\le i<k,\ 1\le x\le2h\}.
$$

从根向左三格，接第负三列竖干，向下延伸至第 $2(k+h)$ 行。对每个 $1\le j\le h$，在行 $y_j=2(k+j)$ 向左挂长 $2j$ 的横段，再从左端向上挂长 $2(k-1)$ 的竖臂。全部道路同时作为查询和宿主。

较晚钩子的竖臂在早横段左端之外至少两格，其横段在早竖臂底端之下至少两格。竖臂顶端均在第四行或更下方，不接触第零行连接桥。故没有额外四邻接或环。直接计数得

$$
N=4kh+h^2+4k+h+2,\qquad
n=\max\{2(k+h)+1,4h+4\}.
$$

在第 $j$ 个横段上取

$$
\begin{aligned}
b_{j,\ell}&=(y_j,-3-2j+\ell),&1\le\ell\le2j,\\
q_{i,\ell}&=(2i,\ell),&0\le i<k,\\
a_{i,j}&=(y_j-2i,-3-2j).
\end{aligned}
$$

从宿主源点到目标全程朝根移动，读出查询词 $\mathrm S^{2i}\mathrm E^\ell$。这些查询点在不同横齿上，互不可比。严格后代只能继续向右；更长匹配的最后横段必须经过当前钩左端再向左一格，而该格为空。因此它们均为极大前沿，得到

$$
E\ge kh(h+1),\qquad E_{\mathrm{ns}}\ge(k-1)h(h+1).
$$

第二式只计先向下再向右的非直线前沿。实际上，指定横段目标恰有上述前沿；左竖臂、非接齿竖干、桥及右梳的非根目标各只有一个前沿，根恰有两个。因此

$$
E=N+(k-1)h(h+1)+1.
$$

取 $k=h=t$，即得

$$
n=4t+4,\qquad N=5t^2+5t+2,\qquad
E=t^3+5t^2+4t+3=\Theta(nN).
$$

故一般的 $E=O(N)$、$E_{\mathrm{ns}}=O(N)$，乃至 $E=O(n^2)$ 都不成立。与线性前沿界等价的固定容量内部路径收费方案也随之被否定。

### 完整前缀与实际检查量

若较早访问了另一查询齿的非零列点，其根路径也全部已访问。将当前齿点送到某个指定目标时，旧齿若更浅，就要求在左竖臂上提前右转，第一格为空；内钩至少再向右两格。旧齿若更深，就要求越过当前钩底端，下一格也为空；外钩至少再向下两格。因此任何真实发现序中，所有指定成功事件只能来自同一个齿号，总数至多 $h(h+1)$。先访问一条根到齿尖的路径即可达到它。

直接纯上行匹配数也没有超过目标量级。固定宿主源点，贡献是最长可读查询前缀长度加一。左臂先读到钩底，距离为偶数时再读横段；横段只读剩余向右段；右梳横点最多读三步向左；连接桥的三个源点共读六步。平衡参数 $t\ge2$ 时，求和恰得

$$
S_{\mathrm{up}}=\frac{11}{3}t^3+\frac{19}{2}t^2+\frac{17}{6}t+8
=\Theta(nN).
$$

此外分叉点恰有 $k+h-2$ 个，既有长分枝界对任意实际访问顺序给出

$$
W\le(6n+k+h-7)N=O(nN).
$$

所以本族关闭的是无权前沿线性这一辅助路线。一般的直接根路径总量和真实完整前缀检查量仍待研究，原复杂度的对数差距尚未消除。