题目理解

我们有一棵以城市1为根的树，每个城市有一个危险度（深度）。需要处理三种操作：

1. 移居：将某个危险度 $X$ 的所有城市的海狸移动到危险度 $Y$ 的对应祖先城市
2. 接纳移民：在某个城市增加海狸数量
3. 调查：查询某个城市的海狸数量，并清空该子树

关键观察

1. 树结构特性

• 树是外向树（所有边指向父节点）
• 每个节点的危险度就是其深度
• 从危险度 $X$ 移动到 $Y$ 意味着将所有深度为 $X$ 的节点合并到它们在深度 $Y$ 的祖先

2. 操作分析

• 移居操作：实际上是合并两个深度的所有节点
• 调查操作：查询并清空子树，这暗示了海狸移动的累积性

算法核心

数据结构设计

map<int, int> f[N];  // f[d][dfn] = 海狸数量

这里：

• f[d] 存储深度为 d 的所有节点的海狸数量
• 键是DFS序 dfn，值是海狸数量
• 使用DFS序可以高效处理子树操作

算法流程

步骤1：DFS预处理

void dfs(int u) {
    dfn[u] = ++tot;           // DFS进入时间
    for (auto i : v[u])
        d[i] = d[u] + 1, dfs(i);  // 计算深度
    low[u] = tot;             // DFS离开时间
}

通过DFS序，可以快速判断节点间的祖先关系：

• 节点 v 在节点 u 的子树中 ⇔ dfn[u] <= dfn[v] <= low[u]

步骤2：处理操作

移居操作 (op == 1)：

if (f[x].size() > f[y].size())
    swap(f[x], f[y]);        // 启发式合并
for (auto i : f[x])
    f[y][i.first] += i.second;  // 合并海狸数量
f[x].clear();                // 清空源深度

接纳移民操作 (op == 2)：

f[d[x]][dfn[x]] += y;  // 在对应深度的DFS位置增加海狸

调查操作 (op == 3)：

auto i = f[d[x]].lower_bound(dfn[x]);  // 找到子树起点
while (i != f[d[x]].end() && i->first <= low[x])
    sum += i->second, i = f[d[x]].erase(i);  // 累加并清空子树
cout << sum << "\n", f[d[x]][dfn[x]] = sum;  // 输出并重新设置

算法正确性

1. 移居操作的正确性

• 深度 $X$ 到深度 $Y$ 的移动：由于树是外向树，每个深度 $X$ 的节点都有唯一的深度 $Y$ 祖先
• 启发式合并确保复杂度：总是小的合并到大的

2. 调查操作的正确性

• 使用DFS序范围 [dfn[x], low[x]] 精确匹配子树
• 清空后重新设置：因为后续操作可能继续向该节点添加海狸

3. 数据结构选择

• map 维护有序性，支持范围查询和删除
• DFS序保证同深度节点按子树顺序排列

时间复杂度分析

操作复杂度

• 移居操作：$O(\min(|f[x]|, |f[y]|) \log n)$，启发式合并保证总复杂度 $O(n \log^2 n)$
• 接纳移民：$O(\log n)$
• 调查操作：$O(k \log n)$，其中 $k$ 是删除的元素个数

总体复杂度

在 $N, Q \leq 2 \times 10^6$ 的限制下，算法可以通过：

• 启发式合并保证总合并复杂度
• 每个海狸最多被移动和删除一次

关键优化技术

1. 启发式合并：确保合并操作的高效性
2. DFS序：高效处理子树操作
3. 延迟更新：调查时才实际计算子树和

算法标签

• 启发式合并
• DFS序
• 子树处理
• 延迟更新
• 树形结构

算法优势

1. 简洁高效：利用树的性质和DFS序简化操作
2. 启发式优化：自动选择最优合并策略
3. 范围处理：利用DFS序高效处理子树

总结

该算法通过巧妙的DFS序和启发式合并技术，解决了大规模树形结构上的动态合并和查询问题。核心思想是将节点按深度分层，利用DFS序处理子树关系，通过启发式合并保证操作效率。算法设计简洁而高效，充分体现了树形结构问题的经典处理方法。