# 字典序最大的树标号：题解

## 解法与贡献

首选出题人的“按结点编号分配区间”算法：倍增找已处理祖先、树状数组维护剩余子树大小、占位线段树确定可用区间。Codex（GPT-6）补充完整不变量证明、迭代遍历和按题目指定模数的实现，并提供基于祖先集合的静态排序补充解法。倍增、树状数组、线段树、持久化和康托展开均为经典方法；贡献指它们在本题中的建模、证明与实现。


下图为样例一的最优方案，每个结点标为“结点编号：标号”。

![ 算法示例 ](assets/example.svg)

## 为什么要整块分配最大的标号

考虑一棵尚未分配的树或森林，可用标号是一段连续区间 $[L,R]$ .其中编号最小的结点为 $x$ ，它在当前森林中的子树大小为 $s$ .

有 $s-1$ 个后代必须比 $x$ 大，所以 $a_x\le R-s+1$ .这个上界可以达到：给整个子树分配最大的 $s$ 个标号，令 $a_x=R-s+1$ ；子树内部按任意合法堆序分配，其余结点使用较小的标号。其余结点中若有 $x$ 的祖先，它们也恰好需要更小的标号。

由于 $x$ 是当前最先比较的结点，最优解必须取这个上界。这又强制它的所有后代使用全部较大的 $s-1$ 个标号。于是问题分成两部分：该子树去掉根后的森林，以及删除整棵该子树后的剩余森林；各自使用确定的连续标号区间，继续同样的选择。

该论证同时给出贪心的上界、达到上界的构造，以及两个递归部分互不影响的原因。

## 首选：按编号扫描，动态维护区间

依次处理结点 $1,2,\ldots,N$ .已处理结点成为分隔点。对未处理结点 $u$ ，记 $t$ 为它最近的已处理严格祖先；不存在时用虚根零。

删除已处理结点后，$u$ 所在的未处理连通块归属于 $t$ .维护以下不变量：

1. 每个已处理结点 $t$ 保存一个分配区间 $[a_t,r_t]$ ；虚根取 $a_0=0,r_0=N$ .
2. 归属于 $t$ 的未处理连通块使用从 $a_t+1$ 开始的一个连续空闲前缀。已从中分走的子块占据后面的区间，各自的根标号已被标记为占用。
3. $s_u$ 是 $u$ 下方、不经过任何已处理结点的未处理结点数。

设 $b$ 为 $[a_t+1,r_t]$ 内最小的已占用标号，若没有则取 $r_t+1$ .当前连通块的空闲区间恰好以 $b-1$ 结尾。前述整块贪心因此给出

$$a_u=b-s_u,\qquad r_u=b-1$$

把 $a_u$ 标为占用。新块的根确定了，它内部剩余部分归属于 $u$ ；原连通块只失去末尾这 $s_u$ 个标号。因此三个不变量继续成立。

### 最近的已处理祖先

处理 $u$ 时，已处理恰好指结点编号小于 $u$ .预处理倍增父亲及每段祖先中的最小编号，从大到小尝试跳过“所有祖先编号均大于 $u$”的段。最后停留位置的父亲就是 $t$ .虚根编号零阻止越过根。

### 剩余子树大小

先求原子树大小，以及 DFS 的进入时刻 $\operatorname{in}(v)$ 和退出时刻 $\operatorname{out}(v)$ .两类时刻均占一个编号，总计 $2N$ 个时刻。

设树状数组的前缀和为 $F$ ，则

$$s_u=\operatorname{size}(u)+F(\operatorname{in}(u))-F(\operatorname{out}(u))$$

当分走以 $u$ 为根、大小为 $s_u$ 的剩余子块时，仅需将 $t$ 与 $u$ 之间的未处理严格祖先的剩余大小减去 $s_u$ .若 $t$ 就是父亲，无需更新；否则做两次点加：

$$\operatorname{add}(\operatorname{in}(t)+1,-s_u),\qquad
\operatorname{add}(\operatorname{in}(u),s_u)$$

它使 $F$ 在半开时刻区间 $[\operatorname{in}(t)+1,\operatorname{in}(u))$ 减少 $s_u$ .对路径上的严格祖先，其进入时刻在该区间内而退出时刻在外，所以进入与退出前缀和之差减少 $s_u$ .旁支的两个时刻要么同在其中，要么都不在其中，差值不变；$t$ 与 $u$ 本身也不变。这正是所需的路径效果，不能只把树状数组理解为简单子树加。

### 占位线段树

每个区间只记录是否包含已占用标号。插入根标号时沿路径标记；查询 $[a_t+1,r_t]$ 内第一个占用位置时优先访问左子树，跳过空段和区间外部分。单次操作 $O(\log N)$ .

## 补充：祖先集合的静态排序

给结点 $v$ 定义一个长为 $N$ 的二进制键 $B_v$ ：从根到 $v$ 的路径包含编号 $i$ 时，第 $i$ 位为一，否则为零。按 $B_v$ 的字典序降序排列结点，一优先于零，然后依次赋标号 $N,N-1,\ldots,1$ .

后代的祖先集合严格包含祖先的集合，所以其键更大、标号也更大，堆序成立。最优性由前面的整块贪心得到：在当前尚未决定的组内，编号最小的结点 $x$ 对应最早可能不同的比特；拥有该比特的恰好是它的子树，静态排序将它们全部放在较大标号一侧。两边递归使用下一位有区别的编号，正好执行同一整块分配。因此此排序得到唯一的最优标号数组。

无需显式保存 $N$ 位键。用持久化线段树表示集合：结点 $v$ 的版本由父亲版本加入编号 $v$ 得到，空子树指针为零。比较两版本时，若左孩子指针不同就去左边，否则去右边，找到第一个不同的比特；该处非空的一方更大。

这里指针比较是精确判断，没有哈希碰撞问题。两条根路径先共享一段，然后分别加入互不相交的结点编号。对于任意编号区间，如果分叉后两边都没有加入该区间内的编号，就保留相同的旧指针；只要某一边有加入，两边的集合就不同，因为另一边不可能加入同一个编号。祖先与后代版本的比较是其中一边没有新增编号的特例。

构建版本需 $O(N\log N)$ 时间和空间；一次比较 $O(\log N)$ ，排序总时间 $O(N\log^2 N)$ .它的数学描述较统一，但多一个排序对数因子。首选 [std.cpp](std.cpp) 的 $O(N\log N)$ 时间；[alternative.cpp](alternative.cpp)提供完整静态方案，作为显著不同的补充思路。

## 康托排名与实现边界

从编号 $N$ 倒序扫描，用另一棵树状数组维护已经出现的标号。查询严格小于 $a_i$ 的个数 $c_i$ ，贡献为 $c_i(N-i)!$ .阶乘可沿扫描方向滚动计算，对两个指定模数分别累加；此处不需要模数为素数，也不需要逆元。

首选方案总时间 $O(N\log N)$ ，空间 $O(N\log N)$ .所有原树遍历使用显式栈，链形树不会产生线性深度的函数递归；线段树递归仅有对数深度。模乘提升到六十四位，两个模数分别为 $100000007$ 与 $100000009$ .