超好的一道支配树题目。来源：2019多校赛第三场B题。

题目描述

        Country A and B are at war. Country A needs to organize transport teams to deliver supplies toward some command center cities.
        In order to ensure the delivery works efficiently, all the roads in country A work only one direction. Therefore, map of country A can be regarded as DAG( Directed Acyclic Graph ). Command center cities only received supplies and not send out supplies.
        Intelligence agency of country B is credibly informed that there will be two cities carrying out a critical transporting task in country A.
        As long as any one of the two cities can not reach a command center city, the mission fails and country B will hold an enormous advantage. Therefore, country B plans to destroy one of the n cities in country A and all the roads directly connected. (If a city carrying out the task is also a command center city, it is possible to destroy the city to make the mission fail)
        Now country B has made q hypotheses about the two cities carrying out the critical task.
Calculate the number of plan that makes the mission of country A fail.

输出格式

        The first line contains a integer T (1≤T≤10), denoting the number of test cases.In each test case, the first line are two integers n,m, denoting the number of cities and roads(1≤n≤100,000,1≤m≤200,000).
Then m lines follow, each with two integers u and v, which means there is a directed road from city u to v (1≤u,v≤n,u≠v).
        The next line is a integer q, denoting the number of queries (1≤q≤100,000)
And then q lines follow, each with two integers a and b, which means the two cities carrying out the critical task are a and b (1≤a,b≤n,a≠b).
        A city is a command center if and only if there is no road from it (its out degree is zero).

输出格式

        For each query output a line with one integer, means the number of plan that makes the mission of country A fail.

输入输出样例

Sample input

2
8 8
1 2
3 4
3 5
4 6
4 7
5 7
6 8
7 8
2
1 3
6 7
3 2
3 1
3 2
2
1 2
3 1

Sample output

4
3
2
2

题解

        题目就是给一张DAG，其中没有出边的点称为指挥站，每一个点都可以通过沿图中的边走向指挥站。现在选定两个点，并删除图中任意一个点（可以是选定的点），使这两个点不都能通向任意一个指挥站，求删点的方案数。
        既然只能删去一个点就能让这个点不能达到令一些点，那么这个被删去的点必然是必经点，看到必经点立即想到支配树，于是这题就可以拿支配树解决了。
        首先从所有的指挥站出发，向一个新结点（不妨称为超级指挥站）连边，然后将图反建。现在要删去一个点，使得某个点与任何一个指挥站都不联通，如何解决？答案显然就是超级指挥站到该点的必经点，方案数自然就是这些必经点的数量再减去一（不能删超级指挥站，那是我们自己加的）。
        在反建的图上建支配树，DAG上的支配树比较容易建出，于是我们得到一棵树，它以超级指挥站为根。建立支配树的复杂度为$O(nlogn)$。
        现在求两个点不都能走向超级指挥站的必经点数量，答案显然就是支配树上两个点到根的路径上的点的数量，不要忘了减去根。由于有多次询问，可以先一遍DFS预处理所有结点到根的结点数，然后用lca（倍增法）求点的数量，这一步复杂度为$O(qlogn)$，然后本题就切掉了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>

using namespace std;
struct Edge {
    int next, to;
} edge[200005], edge_opp[200005], edge_tree[200005];
int head[100005], head_opp[100005], cnt1, cnt2, cnt3, n, m, in[100005], head_tree[100005], dep[100005];
int gd[100005][25], ss[100005];
vector<int> vvp;
queue<int> que;

inline void add(int x, int y) {
    edge[cnt1].to = y, edge[cnt1].next = head[x], head[x] = cnt1++;
}

inline void add_opp(int x, int y) {
    edge_opp[cnt2].to = y, edge_opp[cnt2].next = head_opp[x], head_opp[x] = cnt2++;
}

inline void add_tree(int x, int y) {
    edge_tree[cnt3].to = y, edge_tree[cnt3].next = head_tree[x], head_tree[x] = cnt3++;
}

inline int read() {
    char e = getchar();
    int s = 0;
    while (e < '-')e = getchar();
    while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
    return s;
}

inline void topSort() {
    que.push(0), vvp.clear();
    while (!que.empty()) {
        int f = que.front();
        que.pop(), vvp.push_back(f);
        for (int i = head[f]; i; i = edge[i].next) {
            --in[edge[i].to];
            if (in[edge[i].to] == 0)que.push(edge[i].to);
        }
    }
}

inline int LCA(int x, int y) {
    if (dep[x] > dep[y])swap(x, y);
    for (int i = 24; i >= 0; i--)if (dep[gd[y][i]] >= dep[x])y = gd[y][i];
    if (x == y)return x;
    for (int i = 24; i >= 0; i--)if (gd[x][i] != gd[y][i])x = gd[x][i], y = gd[y][i];
    return gd[x][0];
}

void DFS(int x, int s) {
    ss[x] = s;
    for (int i = head_tree[x]; i; i = edge_tree[i].next)DFS(edge_tree[i].to, s + 1);
}

int main() {
    int t = read();
    while (t--) {
        n = read(), m = read(), memset(head, 0, sizeof(head)), memset(head_opp, 0, sizeof(head_opp));
        cnt3 = cnt1 = cnt2 = 1, memset(in, 0, sizeof(in)), memset(head_tree, 0, sizeof(head_tree));
        for (int i = 1, x, y; i <= m; i++) {
            x = read(), y = read();
            add(y, x), add_opp(x, y), ++in[x];
        }
        for (int i = 1; i <= n; i++)if (in[i] == 0)add(0, i), add_opp(i, 0), ++in[i];
        dep[0] = 1, topSort();
        for (int i = 1; i <= n; i++) {
            int s = edge_opp[head_opp[vvp[i]]].to, lca = s;//第一个前驱
            for (int j = edge_opp[head_opp[vvp[i]]].next; j; j = edge_opp[j].next)lca = LCA(lca, edge_opp[j].to);
            add_tree(lca, vvp[i]), dep[vvp[i]] = dep[lca] + 1, gd[vvp[i]][0] = lca;
            for (int j = 1; j < 25; j++)gd[vvp[i]][j] = gd[gd[vvp[i]][j - 1]][j - 1];
        }
        DFS(0, 0);
        int q = read();
        while (q--) {
            int a = read(), b = read();
            int lca = LCA(a, b);
            printf("%d\n", ss[a] + ss[b] - ss[lca]);
        }
    }
    return 0;
}