GitHub 源文件 Markdown

嵌套梳状族的参数证明

本文研究一族真实诱导四邻接树及真实行星心。它否定跨参考轴像直接相加完整资源大小的常数倍道路预算，不否定候选算法的目标复杂度。参数结论来自构造证明；固定输入检查只作复核。

1. 查询和指定候选

取

\[ k\ge6,\quad t\ge1,\quad w\ge3,\qquad D=6w,\quad R=D+3,\quad s=2w+5,\quad d=3s. \]

用行、列表示坐标，向下增加行坐标。标签为

\[ h=(0,d). \]

一条右梳从根向下走到给定深度，每下行三步，向右走给定宽度并原路返回，最后沿竖干返回根。左梳把横向方向反过来。两者非根点数均为

\[ B=D+(D/3)w=2w^2+6w. \]

右梳的非根相对点集是

\[ H_+=\{(j,0):1\le j\le D\} \cup\{(3j,x):1\le j\le D/3,\ 1\le x\le w\}. \]

左梳的点集记为

\[ H_-=\{(j,-x):(j,x)\in H_+\}. \]

查询从原点开始：

1. 逐层下行一个行距、右二，完整访问右梳，再左二回到主竖干。共访问指定数量的层。
2. 在最底层右行一个相位，访问左梳；再右行一个标签，访问另一条左梳；左行回到主竖干，再上行一层。
3. 从倒数第二层向上逐层处理：右行标签长度加二，访问右梳，返回主竖干，上行一层。最后回到原点。

上层指定源、底层指定源分别为

\[ a_{i,j}=(-iR,5sj),\quad 1\le i<k,\quad0\le j<t, \]

\[ a=(-kR,c),\quad c\in\{0,s,\ldots,P_c\},\qquad P_c=5s(t-1),\quad b=P_c/s+1. \]

上层源指定早端是自己对应层右梳的最后一个齿端；底层源指定早端是第一条特殊左梳的最后一个齿端：

\[ e_i=(iR+D,2+w),\qquad e_k=(kR+D,s-w),\qquad f=e+h. \]

道路严格按这些指定配对的完整前缀定义：

\[ F=\bigcup_{(a,e,f)} \bigl((a+P_{t(f)})\cup(a+h+P_{t(e)})\bigr). \]

指定候选的两份完整匹配从定义即成立；真实星心仍需另证。

不同查询梳和各横臂只在指定根相连。直接计数得到

\[ |Q|=1+kR+kd+2(k-1)+s+(2k+1)B, \qquad m=2|Q|-2+4k. \]

额外步数来自重复访问每层初始的两条横边，已计入真实移动数。

2. 道路分解与诱导性

把上述并集展开，可得到以下全部道路片段。

负行和零行。 负行的主竖干在相位列上；列相位指标集合是

\[ L=\{0,\ldots,b-1\}\cup\{3,\ldots,b+2\}. \]

每条竖干从最负行走到零行，即

\[ -kR\le r\le0. \]

在以下各层先右二，再挂右梳：

\[ -(k-1)R,\ldots,-R,0. \]

零行同时有整条水平路

\[ \{(0,c):0\le c\le P_c+4s\}. \]

零行左梳根的相位指标集合为

\[ L_-=\{1,\ldots,b\}\cup\{4,\ldots,b+3\}. \]

当每上层只有一组源时，这些相位集合可能有空缺，不能把它们误写成整段指标。

正行。 对每个上层源列，从零行延伸主竖干至倒数第二层正行。在每个正层，有横臂从该源列一直伸到四个相位之外，并挂上短右梳和两条左梳；除最后一个正层外，还挂标签加二处的长右梳。因此每个列组的横坐标都落在

\[ [5sj,5sj+4s],\qquad 0\le j<t. \]

相邻组之间至少空出一个相位。在最靠近零行的高度带，零行的左梳竖干可能与正行主竖干重合；该处梳齿向左，只会给竖干添加树枝。

横向两种相邻梳齿的相位区间为

\[ [2,w+2],\qquad [s-w,s]=[w+5,2w+5]. \]

最近端点相隔三列，不产生额外单位边。纵向两层相隔一个行距，而每条梳只有给定深度，所以相邻层也留出三行间距。每条梳内部的齿间隔三行。由此，上述片段之间只有指定的根、主竖干重合与零行连接，没有额外四邻接边。把梳逐条挂到竖干和横臂上，所得是连通诱导树。

负行各层、各相位列上的右梳非根集互不交，其数量与轴类数乘列组数同阶。所有片段总量也同阶，因为梳大小已控制行距和相位长度。因此

\[ N=\Theta(ktB),\qquad n=\max\{(2k-1)R+D+1,\ (5t-1)s+1\}. \]

这些常数不依赖三个参数。

3. 全部真实行星心

对固定正标签，完整标记表如下；未列出的点不会给出这个标签的行星心。

源	早端	晚端
上层指定源	对应层横臂的零、一、二列	早端加标签
上层指定源	对应层右梳的全部非根点	早端加标签
每个底层源	最底层横臂的零至相位减一列	早端加标签
每个底层源	最底层第一条左梳的全部非根点	早端加标签
最右底层源	最底层第一条左梳的根	早端加标签

首先，任意有关晚候选都已完成最底层第一条左梳。初始查询包含一个完整行距的下行和右二。普通梳竖干比行距短，梳齿更不能提供这样的初段。因此候选根必须在相位列和整层行。要完成整条初始主竖干，正行源不可能成功；负行源若不在指定上层列组，就只能从最底层源行开始。底层配对又要求标签平移源也具有初始竖段，因此两源的列相位指标都必须属于主竖干集合；相差三个相位的配对交集恰好是指定底层列区间。故能参与这个标签配对的晚源恰好来自表中的源。这里只分类参与配对的候选，不排除其他时刻还存在未生成该标签标记的候选。

对于一个上层源，标签平移后的候选在过零行之后无法再下行整个行距：它的列比上层列组多三个相位，不属于任何正行主竖干。所以早端不能在更后面的查询层。更前面的查询层的晚端又要求负行出现长横臂，而负行仅有短横臂，故只能使用源自己的层。上层梳的同一行中，更早的其他点与当前点的列差严格小于相位；它们会把候选根移到非相位列，无法匹配初段。因此这些指定早端确实是星心。

底层轴点按列模相位区分，零至相位减一列各给一个星心。相位处的根点会被下一底层源提供的零列星心遮盖，只有最右源没有这个后继。特殊左梳的列相位与普通右梳相隔三列；两区间间的差也严格小于相位。所以任何更早的普通右梳点或特殊梳点，都不能提供另一个合法相位根。每个特殊梳点也是真实星心。查询的横坐标范围同时排除了其他标签配对。

于是

\[ \widetilde M_h=(k-1)t(B+3)+b(B+s)+1. \]

所有标记都通过同一个严格切口：最晚早端是第一条底层特殊梳的最后齿端；此前最大查询列为一个相位，小于标签。故

\[ \tau=t_*+1,\qquad |R_{\rm common}|=kR+2k+s-1+(k+1)B. \]

4. 筛选后的超额和资源重复计数

所有标记的宿主交域含零行轴，最短周期为一，幂次为标签长度。上层每类有

\[ t(B+1) \]

笔长早资源标记：零列、一列轴点被排除，二列点及全部右梳点保留。底层长类有

\[ b(B+s-2)+1 \]

笔，是最大类。按相同大小时先支付较晚层的约定，标签证明的规则支付底层和最下面三个上层类；其余为

\[ R^{(24)}=(k-4)t(B+1). \]

在这份实际余项内，参考轴是剩下的最晚层。删去它后剩余的源恰为

\[ 1\le i\le k-5,\quad0\le j<t. \]

每个源都有完整右梳，点块后的超额为

\[ R^{(27)}=(k-5)t(B-d)=(k-5)t(2w^2-15)>0. \]

每个剩余源使用过的最大真实早资源大小是

\[ |S_{i,j}^{\max}|=1+i(R+2+B). \]

因此

\[ \sum_{i,j}|S_{i,j}^{\max}| =t\left((k-5)+(R+2+B)\frac{(k-5)(k-4)}2\right) =\Theta(tk^2B) \]

在轴类数趋于无穷时，比道路点数多一个轴类数因子。共同早树副本的大小和同样为

\[ (k-5)t|R_{\rm common}|=\Theta(tk^2B). \]

这确实是跨不同实际参考轴像的重复计费：对源而言，参考轴像行坐标为

\[ (k-4-i)R. \]

同层不同列组的实际参考轴段位于互不连通的水平臂，因而也是不同宿主轴像；不能只按几何直线是否同一行判定 Cayley 树中的轴相同。每个参考像只有一个剩余源，所以先按参考像取资源并，也不能减少上述求和。标签证明第 37 节的“同像内不交”全部满足。

取三个参数同时增长：

\[ k=t=w\longrightarrow\infty,\qquad n=\Theta(w^2),\quad N=\Theta(w^4),\quad \sum |S_{i,j}^{\max}|=\Theta(w^5). \]

因此“筛选后跨参考像的最大早资源并大小和为常数倍道路数”这个结论不成立。

5. 标记仍有单位分配

每个上层标记都分配到其源第一次访问的短横臂或右梳上的对应相对点：

\[ (iR,x)\mapsto a+(R,x),\quad 0\le x\le2, \]

\[ (iR+j,2+x)\mapsto a+(R+j,2+x),\quad(j,x)\in H_+. \]

这些点都在相应完整早资源中。底层零、一、二列轴点同样分配到第一条短横臂；其他底层轴点与全部特殊左梳点用自身早端像。

不同源层落在不同高度带，带间隔三行。不同源列组相隔五个相位。正行特殊左梳的相位区间与上层首次右梳相隔三列；额外底轴点又位于第一条短臂之外。最右底轴根只出现一次。这逐项排除了分配点碰撞。

因此全部标记都有显式单位资源分配。跨参考像的粗资源求和失败，并不意味着标记费用无界。

算法在此族也可直接计数。第一次下行扫描全部道路；初始直段的后续扫描至多为道路竖边数乘行距，即

\[ O(ktD^2). \]

完成初始右二后，候选必须从整层行、相位列开始，候选数为轴类数乘列组数的常数倍。此后扫描数至多候选数乘查询点数，得到

\[ W=O(k^2tB). \]

反向下界用每个上层列组的全部源层。这些源均存活至整段最初梳状查询结束，共有

\[ kt \]

个候选，每个通过

\[ \Theta(kB) \]

次首次访问。因此

\[ W=\Theta(k^2tB). \]

在三个参数同时增长的选择下，

\[ W=\Theta(w^5)=\Theta(n^{5/2}),\qquad m=\Theta(w^3)=\Theta(n^{3/2}). \]

没有超过目标三次界。

参数族的渐近结论针对允许规模增长的数学模型；用于运行正式程序的输入仍须满足题面限制。

代表性输入

nested-combs-k7-t3-w4.in

使用 verify_examples.py 检查道路森林、移动、候选数与候选检查次数。有限输入只用于复核，不替代上面的参数证明。