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

解法与贡献¶

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

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

算法示例

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

考虑一棵尚未分配的树或森林，可用标号是一段连续区间 \([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\) .维护以下不变量：

每个已处理结点 \(t\) 保存一个分配区间 \([a_t,r_t]\) ；虚根取 \(a_0=0,r_0=N\) .
归属于 \(t\) 的未处理连通块使用从 \(a_t+1\) 开始的一个连续空闲前缀。已从中分走的子块占据后面的区间，各自的根标号已被标记为占用。
\(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 的 \(O(N\log N)\) 时间；alternative.cpp提供完整静态方案，作为显著不同的补充思路。

康托排名与实现边界¶

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

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