题目链接
题目大意：给你一个n个点，m条边的有向无环图，q次询问。每次询问给出两个点x和y，要求在图上删掉一个点及这个点连的所有边，使得x和y中至少有一个点和所有出度为0的点不连通，问有多少种删法。n ≤ \le ≤ 1e5，m ≤ \le ≤ 2e5，q ≤ \le ≤ 1e5。
难度：Ag
分析：
看到出度为0、不连通这种关键字，就应该想到支配树。
先说一下什么是支配树，一个有向图的支配树，首先是这个图的树形图，然后满足一个性质：如果在图上删去一个点及这个点连的所有边，那么这个点在支配树上的所有后代，都和树形图的根节点在原图中不连通。
假设我们已经会求一个图的支配树，考虑如何解这道题。题目要求x和y与所有出度为0的点不连通，所以支配树的根节点应该和这些点有关。因为x和y每次询问都会变，所以支配树的根节点不会是x或y。考虑出度为0的点，由于题目要求与所有出度为0的点不连通，所以支配树的根节点也不能是某个出度为0的点，我们需要一种方法，使得所有出度为0的点都近似成为支配树的根节点。
为了达到上述目的，我们选择新建一个点p，然后所有出度为0的点向p连一条边，这样p就可以作为支配树的根节点，和p不连通，就意味着和原图中所有出度为0的点不连通。最后，由于支配树必须是一个树形图，我们发现还需要使原图中所有边方向变反，才能使得树形图存在。
建立支配树后，先要会计算使x不连通的方案数。删去图上某个点之后，这个点在支配树上的所有后代都和支配树根节点p不连通。所以需要计算有多少个点在支配树中的后代节点包括x，显然这个问题的答案是x在支配树中的祖先个数，也就等于x在支配树中的深度。
既然会计算单独使x不连通的方案数和单独使y不连通的方案数，计算x或y不连通的方案数，只需要容斥一下即可。考虑单独使x不连通的方案和单独使y不连通的方案中，有哪些是重复的？显然，x和y的所有公共祖先被重复计算了，只要减掉x和y的公共祖先数量即可，这个数量等于x和y的最近公共祖先的深度。
最后，只剩下一个问题，如何求一个图的支配树？由于这道题保证给出的图为DAG，所以只需要会求DAG的支配树即可，方法如下：首先把根节点加入支配树（根节点的入度一定为0，否则不可能产生树形图），然后按照拓扑顺序依次将DAG上每个点加入支配树，某个点x在支配树上的父亲，就是原图上连了至少一条指向x的边的所有点，它们的最近公共祖先。至此，问题解决，时间复杂度O((m + q) logn)，n为点数，m为边数，q为询问数。
代码：
# include <bits/stdc++.h>
# define MAXN 100005
# define MAXM 200005using namespace std;struct Tree
{int n, m;int to[MAXN << 1]; //链式前向星存树int next[MAXN << 1];int head[MAXN];int depth[MAXN]; //记录每个点的深度int fa[MAXN][20]; //倍增求lca需要预处理的信息int lg2[MAXN];void build(int size){n = size;m = 0;memset(head, 0, sizeof(int) * (n + 1));depth[n + 1] = 1; //将n+1号点视作支配树的根节点for (int i = 1; i <= n; ++i)memset(fa[i], 0, sizeof(fa[i]));