Day10

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

InputThe first line contains a integer $T$ OutputFor each query output a line with one integer, means the number of plan that makes the mission of country A fail.Sample Input

Sample Output

国家A和B处于战争状态。A国需要组织运输队向一些指挥中心城市提供物资。为了确保交付有效，A国的所有道路只能向一个方向发展。因此，国家A的地图可以被视为DAG。指挥中心城市只收到物资而不发送物资。B国的情报机构可靠地获悉，将有两个城市在A国执行关键的运输任务。只要两个城市中的任何一个都无法到达指挥中心城市，任务就会失败，B国将拥有巨大的优势。因此，B国计划摧毁A国的n个城市之一和所有直接连接的道路。（如果执行任务的城市也是指挥中心城市，则可以摧毁城市以使任务失败）现在，B国对这两个执行关键任务的城市提出了q假设。计算使国家A的任务失败的计划数量。

思路：支配树，相当于求2点的lca到出度为0的点的数量，拓扑反向建树，DAG->拓扑排序->从出度为0的点开始反向建树->通过lca，因为该题可能有多个连通块，就把每个出度为0的点连接到一个多源上，方便统计

const int maxm = 1e5+5;

int head[maxm<<1], edgecnt, depth[maxm], grand[maxm][25], n, limit, in[maxm], que[maxm];

struct edge{
    int u, v, nex;
} edges[maxm<<1];

void addedge(int u, int v) {
    edges[++edgecnt].u = u;
    edges[edgecnt].v = v;
    edges[edgecnt].nex = head[u];
    head[u] = edgecnt;
}

void init() {
    edgecnt = 0;
    memset(head, 0, sizeof(head));
    memset(in, 0, sizeof(in));
    memset(grand, 0, sizeof(grand));
    memset(depth, 0, sizeof(depth));
}

void toposort() {
    int l = 1, r = 1;
    for(int i = 1; i <= n; ++i)
        if(!in[i]) que[r++] = i;
    while(l < r) {
        int u = que[l++];
        for(int i = head[u]; i; i = edges[i].nex) {
            if(!--in[edges[i].v])
                que[r++] = edges[i].v;
        }
    }
}

int lca(int a, int b) {
    if(a == b) return a;
    if(depth[a] > depth[b]) swap(a, b);
    for(int i = limit; i >= 0; --i) 
        if(depth[a] <= depth[b] - (1<<i)) b = grand[b][i];
    if(a == b) return a;
    for(int i = limit; i >= 0; --i)
        if(grand[a][i] == grand[b][i]) continue;
        else {
            a = grand[a][i], b = grand[b][i];
        }
    return grand[a][0];
}

void run_case() {
    init();
    int m, u, v, q;
    cin >> n >> m;
    for(int i = 0; i < m; ++i) {
        cin >> u >> v;
        addedge(u, v);
        in[v]++;
    }
    limit = floor(log(n+0.0)/log(2.0))+1;
    toposort();
    for(int i = n; i > 0; --i) {
        int u = que[i];
        if(!head[u]) {
            addedge(0, u);
            depth[u] = 1;
            continue;
        }
        int v = edges[head[u]].v;
        for(int j = edges[head[u]].nex; j; j = edges[j].nex) v = lca(v, edges[j].v);
        depth[u] = depth[v] + 1;
        grand[u][0] = v;
        for(int j = 1; j <= limit; ++j) grand[u][j] = grand[grand[u][j-1]][j-1];
    }
    cin >> q;
    while(q--) {
        cin >> u >> v;
        cout << depth[u] + depth[v] - depth[lca(u, v)] << "
";
    }
    
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int t;
    cin >> t;
    while(t--)
        run_case();
    return 0;
}

View Code