# 动态目录树 题解

解法署名：出题人解法使用边节点 Link-Cut Tree 与边复用；Codex（GPT-6）负责多点最近公共祖先、辅助祖先下传、端点映射的实现及证明说明。

## 解法比较

### 出题人解法：边节点 Link-Cut Tree

出题人解法把每条边拆成一个带权辅助节点，用 Link-Cut Tree 维护路径和；换根使用路径翻转，搬移时切断子树的父边，再复用该边节点连接新父亲。改权时通过最近公共祖先和路径前驱判断两点是否直接相邻。操作与正确性说明见下文。

多点查询的出题人解法计算输入序列中每对相邻节点的最近公共祖先，再取其中**结构深度最小**的一个；单点查询直接使用该点。令全部查询点的最近公共祖先为 $c$ .所有相邻对的祖先都在 $c$ 的子树中；若某个查询点就是 $c$ ，与它相邻的一对便得到 $c$ ；否则查询点必在 $c$ 的至少两个儿子子树中，输入顺序中必有一对相邻点跨越这两个分组。因此最浅者恰好是 $c$ .出题人实现按根路径上的原节点个数比较深度，而非按带权距离比较，所以这一结论适用于负边权。

设 $K$ 为查询节点数总和。使用标准 Link-Cut Tree 操作时，总时间为摊还 $O((n+m+K)\log(n+1))$ ，空间为 $O(n)$ .伸展前的下传只沿辅助祖先链进行；越过辅助树根继续沿路径父指针遍历，会引入不在这一摊还分析内的额外开销。

### 实现要点

Codex 实现把多点查询采用逐次合并最近公共祖先，省去额外的节点计数和逐个深度比较；显式保存当前根，并在每次伸展前只沿辅助祖先链下传标记，使实现对应标准操作的证明。路径和采用 64 位整数。

Codex 实现还用端点对到边节点的有序映射判断边是否存在，使改权和搬移后的边信息更新更直接。代价是额外的线性空间常数及映射查找、插入开销。两种实现使用同一套动态树算法，没有直接计时对照。

## 公共路径与最近公共祖先

在当前根 $r$ 下，根到若干节点的公共部分，恰好是根到这些节点最近公共祖先的路径。可依次合并：先令 $c=a_1$ ，再令 $c=\operatorname{LCA}(c,a_i)$ .

这是关于路径交集的结构结论，与边权的正负无关。不能用最小距离来代替最近公共祖先，负边权下两者没有这种对应关系。

## 用边节点维护边权

把每条边 $u,v$ 替换为 $u\!\to e\!\to v$ ，其中辅助节点 $e$ 的点权为该边权，原节点点权为零。于是任意原树路径的边权和就是扩展树路径的点权和。扩展树总共只有 $2n-1$ 个节点。

Link-Cut Tree 将访问路径组织成伸展树，维护左右孩子、父指针、翻转标记、点权和子树点权和。这里的伸展树只是辅助结构，其孩子关系不是题目中的孩子关系。

- `Access(x)` 暴露当前表示根到 $x$ 的路径，并把 $x$ 伸展到辅助树根。
- `MakeRoot(x)` 在访问后翻转整条路径，使表示根变为 $x$ .
- 已知两个节点不连通时，可用 `Link` 连边；已知两点直接相邻时，可用 `Cut` 删边。

在固定表示根下，先 `Access(a)` 再 `Access(b)` ，第二次访问最后处理的辅助路径连接点就是两点的最近公共祖先。实现返回该节点。对于原节点的查询，其最近公共祖先仍是原节点。

## 四种操作

查询前先把表示根设为当前根 $r$ ，再按顺序计算最近公共祖先 $c$ .访问 $c$ 后，辅助树中的路径和就是答案。

换根只需记录新的当前根；下一次需要根的操作会执行 `MakeRoot` .

修改边权时，用有序映射记录无序端点对到边节点的对应关系。若查不到则忽略；否则访问边节点并修改其点权。

搬移前以当前根计算 $\operatorname{LCA}(a,b)$ .它等于 $a$ 当且仅当 $b$ 在 $a$ 的子树内，此时忽略操作，也自然覆盖 $a$ 为当前根和 $a=b$ 的情况。

否则访问 $a$ ，暴露根到 $a$ 的路径。该路径上紧邻 $a$ 的前驱一定是其父边节点 $e$ ，可在辅助树左子树中向右寻找，并立即伸展它。记录的端点确定旧父亲。删除 $e$ 的两条连接，复用同一个边节点，改权后连接 $a\!\to e\!\to b$ ，同时更新端点映射。无需创建越来越多的节点。

由于 $b$ 不在被切下的子树内，新边连接的是两个不同连通块，结果仍是一棵树；子树内部连接均未改变。把子树移回原父亲也是合法操作，此时只会重设这条父边的权值。

## 正确性与复杂度

边节点模型保持所有原节点之间的路径和。上述搬移与换根保持题目定义的无向树和根；映射始终只记录现存边；访问暴露的路径和与公共祖先结论共同保证每次查询正确。伸展旋转前沿辅助祖先链下传翻转标记，避免读到过期的左右关系。

设 $K$ 为全部查询的节点数之和。总时间为 $O((n+m+K)\log(n+1))$ ，为摊还界；空间为 $O(n)$ .伸展的下传与路径前驱搜索都用显式栈或循环，不依赖原树高度的递归。

所用动态树与伸展树可参考 Sleator 和 Tarjan 的 [A Data Structure for Dynamic Trees](https://www.cs.cmu.edu/~sleator/papers/dynamic-trees.pdf) 与 [Self-Adjusting Binary Search Trees](https://www.cs.cmu.edu/~sleator/papers/Self-Adjusting.htm)。

## 验证

独立模型用邻接表直接重建根到节点的路径、取公共前缀和执行搬移。覆盖负权、换根后搬移、移入自身、不存在边、单点和多点查询、空操作序列；正式规模另覆盖长链和重复边复用。

性能测量见[评测环境与性能](../../../docs/评测环境与性能.md)。