题目分析

本题需要维护 $n$ 棵树，支持三种操作：

区间生长：在 $[l, r]$ 范围内的树的生长节点上添加新节点

区间修改生长节点：将 $[l, r]$ 范围内的树的生长节点改为指定节点

查询距离：查询某棵树中两个节点间的距离

算法思路

核心思想：LCT（Link-Cut Tree） + 扫描线 由于直接维护 $n$ 棵树不可行，我们采用全局维护 + 时间轴扫描的方法：

统一建树：将所有操作涉及到的节点预先建立在一棵全局树中

虚拟节点：使用虚拟节点来处理生长节点的修改操作

扫描线处理：将区间操作转化为时间轴上的事件点

关键技巧

1. 节点编号策略

实节点：$1$ 到 $m$ 用于初始节点

虚节点：$m+1$ 开始用于处理生长节点变更

2. 生长节点变更的处理

对于操作 1 l r x：

创建一个新的虚节点 $new$

在时间 $l$ 将 $new$ 连接到 $x$

在时间 $r+1$ 将 $new$ 重新连接到原生长节点

这样在 $[l, r]$ 时间段内，生长节点自然指向 $x$

3. 距离计算 利用 LCT 维护树的形态，通过以下公式计算距离：

dist(u,v)=dep(u)+dep(v)−2×dep(LCA(u,v))

其中 $\text{dep}(x)$ 表示节点 $x$ 到根节点的路径上实节点的数量。

代码结构

1. LCT 实现

cpp

struct LCT {
    int faz[N], ch[N][2], siz[N];
    // 标准 LCT 操作：IsRoot, Rotate, Splay, Access
    int Lca(int x, int y);        // 求 LCA
    int Dep(int x);               // 求深度（实节点数量）
    void Link(int x, int y);      // 连接操作
    void Cut(int x);              // 切断操作
    int Query(int x, int y);      // 距离查询
};

2. 操作处理流程

初始化：

创建第一棵树，生长节点为 $1$

连接虚节点 $m+1$ 到根节点

操作预处理：

0 操作：直接创建新节点并连接到当前生长节点

1 操作：生成两个时间事件（开始和结束）

2 操作：记录查询信息

扫描线执行：

按时间顺序处理所有事件

对于修改事件：执行相应的连接/切断操作

对于查询事件：计算并保存答案

复杂度分析

时间复杂度：$O(m \log m)$

每个操作在 LCT 中的复杂度为 $O(\log n)$

扫描线排序复杂度 $O(m \log m)$

空间复杂度：$O(m)$