GitHub 源文件 Markdown English

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

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

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

当前结论：无权前沿的线性总量界已被否定。 末节给出同根诱导网格树族，其前沿数可达 \(\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\) 中从该点回到根的路径，所以这是真正的完整前缀成功。

由根叶链定理，每个终点至多对应 \(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\)。末节的新构造进一步排除了任何这样的绝对常数。这个满梳族只有线性于方框边长的分叉点，实际算法已由长分枝证明覆盖；前沿构造不是超三次方运行时间反例。

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

继续令道路树同时作为查询与宿主，以 \(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). \]

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