# 局部完整路径的常数容量反例

## 1. 结论与范围

对固定水平标签 $h$，把每个标记的可收费道路点限制为它的完整关联路径
$[a,a+e]\subseteq G_h$。不存在统一常数 $C$，使所有合法实例中的标记都能分配到这些路径上的点、每点容量至多 $C$。

下面的参数族有 $k(k+1)$ 个真实标记，它们的关联路径并集只有 $3k+1$ 个点。因此任何这种分配都需要

$$
C\ge \frac{k(k+1)}{3k+1}\longrightarrow\infty.
$$

这里使用**全部成功、排除查询根**的标记。按查询行选最早星心成立；旧的“根第一子边加查询行”分组也成立，因为查询根只有一个子边。此结论不适用于仅选全局根高度纪录的版本。

同时，这个族满足

$$
M_h=k(k+1),\qquad |G_h|=2k^2+3k,
$$

所以它没有否定整体 $M_h\le C|G_h|$。查询是完整竖直主干加水平直齿，属于已证明 $W\le2nN$ 的旋转梳形子类；它也没有否定原算法的三次方复杂度。

## 2. 坐标、道路与真实走法

本节使用 $(x,y)$ 坐标。取整数 $k\ge2$，令

$$
H=2k,\qquad d=2k+2,\qquad h=(d,0).
$$

查询根为 $(0,0)$。最终查询 $Q$ 是竖干
$x=0,\ 0\le y\le H$，以及每一高度 $y=2i$、$1\le i\le k$ 上从 $x=0$ 到 $x=d+k$ 的水平齿。

实际访问顺序如下，所有线段均逐格行走。

1. 对 $i=1,\ldots,k$，沿竖干向上走两格，到 $(0,2i)$，向右走 $k$ 格，再返回竖干。这样竖干与短齿交替增长。
2. 对 $i=k,k-1,\ldots,1$，从当前竖干位置向右走 $d+k$ 格，返回竖干，再向下走两格。最终回到查询根。

道路 $F$ 是以下整数格点的并集：

- 左竖干：$x=0,-H\le y\le H$。
- 负偶数行上的左短齿：$y=-H,-H+2,\ldots,-2$，$0\le x\le k$。
- 右竖干：$x=d,-H\le y\le0$。
- 非正偶数行上的右短齿：$y=-H,-H+2,\ldots,0$，$d\le x\le d+k$。
- 非负偶数行上的长齿：$y=0,2,\ldots,H-2$，$0\le x\le d+k$。

两条竖干仅由 $y=0$ 的长齿连接。负偶数行左右短齿之间留有至少一列空点；正高度没有右竖干。不同齿间隔一行。因此除已列出的竖干和齿边以外没有诱导邻接，且所有齿都是挂在连接后的双竖干上的路径。$F$ 是一棵诱导树。$Q$ 显然也是诱导树。

逐段去重计数得到

$$
\begin{aligned}
N&=3k^2+kd+6k+1=5k^2+8k+1,\\
|Q|&=k(d+k)+2k+1=3k^2+4k+1,\\
n&=\max(4k+1,d+k+1)=4k+1,\\
m&=(2k+2k^2)+(2k(d+k)+2k)=8k^2+8k.
\end{aligned}
$$

这里 $m$ 包含所有回走步。平移候选 $a_1=(0,-2)$ 的最终完整查询副本在 $F$ 中，所以整个查询始终有真实存活参考。

## 3. 每个指定标记都有完整前缀证书

对 $1\le i\le k$、$0\le j\le k$，定义

$$
\begin{aligned}
e_{ij}&=(j,2i),& f_{ij}&=(d+j,2i),\\
a_i&=(0,-2i),&c_i&=a_i+h=(d,-2i),\\
w_j&=(j,0),&v_j&=(d+j,0).
\end{aligned}
$$

于是 $a_i+e_{ij}=w_j$、$a_i+f_{ij}=c_i+e_{ij}=v_j$。$e_{i0}$ 是非根竖干点，允许作为星心。

### 3.1 早候选 $c_i$ 的完整前缀

发现 $e_{ij}$ 时，竖干只长到高度 $2i$，已访问的旧齿只有更低的短齿，以及当前短齿的已访问部分。

- 竖干经 $c_i$ 平移后落在右竖干的高度区间 $[-2i,0]$。
- 更低短齿经平移后落在负偶数行的右短齿。
- 当前短齿经平移后落在 $y=0$ 长齿的右端部分。

因此 $c_i+P_{e_{ij}}\subseteq F$，包含此前所有访问过的分支。

### 3.2 晚候选 $a_i$ 的完整前缀

发现 $f_{ij}$ 时，整条竖干和所有短齿均已访问；已延长到全长的旧齿恰是高度更高的齿。

- 完整竖干经 $a_i$ 平移后落在左竖干。
- 原有短齿落在负偶数行左短齿或非负偶数行长齿。
- 更高的已延长齿落在正偶数行的长齿。
- 当前正在延长的齿落在 $y=0$ 长齿。

因此 $a_i+P_{f_{ij}}\subseteq F$。特别地，$a_i+P_{e_{ij}}\subseteq G_h$。

### 3.3 最早星心，而非任意一对成功点

在查询行 $y=2i$ 上，$e_{ij}$ 之前被发现的点恰为 $(x,2i)$，其中 $0\le x<j$；$j=0$ 时没有这样的点。

若此前的点要命中同一目标 $v_j$，候选必须是

$$
c'=(d+j-x,-2i),\qquad d+j-x>d.
$$

查询第一步就是 $(0,1)$。其像 $(d+j-x,-2i+1)$ 位于负奇数行，横坐标严格大于 $d$，而道路在这些行只有两条竖干。因此第一步已失败。

所以 $e_{ij}$ 确实是目标 $v_j$ 在该查询行的最早实际成功星心。上述 $k(k+1)$ 个点对全部是真实标记。

## 4. 小路径并集与任意常数容量的失败

每个标记的完整关联路径是

$$
[a_i,w_j]
=\{(0,y):-2i\le y\le0\}\cup\{(x,0):0\le x\le j\}.
$$

所有这些路径的并集恰为

$$
K=\{(0,y):-H\le y\le0\}\cup\{(x,0):1\le x\le k\},
\qquad |K|=3k+1.
$$

它是 $G_h$ 中的连通 L 形子树。$k(k+1)$ 个标记都只能向 $K$ 收费，所以任何常数容量都在足够大的 $k$ 处失败。只取 $j=1,\ldots,k$ 的 $k^2$ 个标记也已足够。

完整早前缀并不都落在这个小 $K$ 中：旧短齿平移后伸向 $K$ 外。它们是真实的前缀约束，并使横向偏移的伪早星心提前失败。局部路径收费把这些外部道路资源排除了。

## 5. 整个标签资源仍足够

直接逐行计算：

- 在 $k$ 个负偶数行中，$G_h$ 各有 $k+1$ 个点。
- 在 $k$ 个负奇数行中，$G_h$ 各只有左竖干的一个点。
- 在 $k$ 个非负偶数长齿行中，$G_h$ 各有 $k+1$ 个点。

因此

$$
|G_h|=k(k+1)+k+k(k+1)=2k^2+3k.
$$

查询交集 $Q\cap(Q-h)$ 仅由每个查询齿的前 $k+1$ 个点组成，大小为 $k(k+1)$。事实上本标签的全部标记恰为第 3 节的 $k(k+1)$ 个标记，证明如下。

任意标记的早点、晚点只能是某个 $e_{ij},f_{ij}$。晚候选必须容纳已访问的完整长 $H$ 竖干，因此其横坐标只能为 $0$ 或 $d$；后者加上晚点横坐标后越过道路右边界。纵坐标必须是偶数，否则已访问的第一个短齿点会落在只有竖干的奇数行。高度为零的候选无法容纳查询最上方短齿，因此晚候选是 $a_s=(0,-2s)$，$1\le s\le k$。

早候选 $a_s+h$ 要容纳高度 $2i$ 的早前缀竖干，必须满足 $s\ge i$。晚候选在当前齿跨过左短齿后的空隙时，必须落在非负偶数长齿行，故必须满足 $s\le i$。于是 $s=i$，仅有第 3 节列出的标记。

因此

$$
\frac{M_h}{|G_h|}=\frac{k(k+1)}{2k^2+3k}<\frac12.
$$

这与小 $K$ 上的密度无界同时成立。它精确区分了已被否定的局部路径收费与仍待解决的整体标签资源计数。

更具体地，本族的全部标记甚至能显式分配到各自的**完整早前缀**，每点容量一：把标记 $(i,j)$ 分配给

$$
z_{ij}=(j,2-2i)=a_i+(j,2).
$$

若 $i=1$，发现 $e_{1j}$ 时当前第一齿已走到 $(j,2)$；若 $i>1$，第一齿已经完整访问。因此 $z_{ij}\in a_i+P_{e_{ij}}\subseteq G_h$。不同 $(i,j)$ 对应不同点。这些点在 $i>1,j>0$ 时都位于小 L 形路径资源 $K$ 外，正是局部路径收费排除掉的那部分已访问道路。

所以本例也没有否定“允许向自身完整早前缀 $a+P_e$ 收费”的单位容量方案；该方案的一般结论仍待证明或反例。

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

## 代表性输入

[local-path-capacity-k2.in](inputs/local-path-capacity-k2.in)

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