题目大意

给定一张 $n$ 个点 $m$ 条边的有向图 $G$，顶点编号从 $1$ 到 $n$。

支配关系：对于两个点 $u, v$，如果从顶点 $1$ 出发到达顶点 $v$ 的所有路径都需要经过顶点 $u$，则称 $u$ 支配 $v$。每个顶点支配自身。

受支配集：对于点 $v$，支配 $v$ 的所有顶点集合称为 $v$ 的受支配集 $D_v$。

现在有 $q$ 次独立询问，每次询问给出一条有向边 $(s_i, t_i)$，需要回答在图中加入这条边后，有多少个顶点的受支配集发生了变化。

算法思路

1. 支配树概念

本题的核心是支配树（Dominator Tree）的构建与应用：

• 在支配树中，每个节点的祖先都是它的支配点
• 一个节点的受支配集就是从根节点（顶点 $1$）到该节点路径上的所有节点

2. 算法框架

步骤一：预处理阶段

1. 构建原图和反图

   • 原图用于正向遍历：v[N] 存储原图的邻接表
   • 反图用于反向分析：rv[N] 存储反图的邻接表

2. 计算可达性矩阵

   • to[i][j]：从点 $i$ 出发是否能到达点 $j$
   • 通过 DFS 遍历计算每个点作为起点时的可达性

3. 确定支配关系

   • 对于点 $j$，如果去掉点 $i$ 后 $1$ 无法到达 $j$，则 $i$ 支配 $j$
   • 将支配关系存储在 idom[j] 中

4. 构建支配树

   • 为每个点找到直接支配点（父节点）
   • 构建树形结构 son[N] 存储每个节点的子节点

步骤二：查询处理

对于每次询问 $(s, t)$：

1. 分析新边的影响机制

   • 新边 $(s, t)$ 可能创建绕过某些支配点的新路径
   • 主要影响：如果存在路径 $fa[u] \to s$ 和 $t \to u$，则 $u$ 可能不再受 $fa[u]$ 支配

2. 标记传播过程

   • 按照支配树的 DFS 序处理节点
   • 如果一个节点的支配关系变化，其子树中所有节点都可能受影响
   • 使用标记 mk[u] 记录节点是否受影响

3. 统计答案

   • 遍历所有节点，统计标记为受影响的节点数量

关键性质

支配树的特性

• 唯一性：每个点有唯一的直接支配点（除根节点外）
• 传递性：如果 $u$ 支配 $v$，$v$ 支配 $w$，则 $u$ 支配 $w$
• 树结构：所有支配关系构成一棵以 $1$ 为根的树

新边的影响条件

加入边 $(s, t)$ 后，点 $u$ 的受支配集改变的条件：

1. $fa[u] \neq 1$ 且 $fa[u] \neq s$ 且 $fa[u] \neq t$
2. 存在路径 $fa[u] \to s$（即 to[fa[u]][s] == true）
3. 存在路径 $t \to u$（即 rev[u][t] == true）

复杂度分析

时间复杂度

• 预处理阶段：$O(n^2 + nm)$
  • 可达性计算：$O(nm)$
  • 支配树构建：$O(n^2)$
• 查询处理：$O(nq)$
  • 每个查询需要遍历所有节点
  • 标记传播过程

空间复杂度

• 图存储：$O(n^2)$
  • 邻接矩阵存储可达性
  • 支配树结构存储

算法优势

1. 理论完备性：基于支配树的经典理论，保证正确性
2. 实现简洁性：避免复杂的 Lengauer-Tarjan 算法，采用更直观的方法
3. 数据范围适配性：对于 $n \leq 3000$ 的规模完全可行

适用场景

• 中小规模有向图的支配关系分析
• 编译器优化中的控制流分析
• 程序分析中的依赖关系计算
• 网络可靠性分析

算法标签

• 支配树
• 图论
• 树上传播
• 动态图分析

总结

本题通过构建支配树将复杂的图论问题转化为树形结构上的分析问题。算法充分利用了支配关系的传递性和树结构的层次性，通过预处理和标记传播高效解决了动态加边对支配关系的影响分析。