题解 P7353 【[2020-2021 集训队作业] Tom & Jerry】

· · 题解

看到“不能经过 Tom 所在的点”，不难想到割点。

对于 Tom 而言，首先可以注意到一种简单的策略：

现在来具体地描述这个“逼”的过程。

我们发现在这种策略下，当 Tom 获胜时，Tom 初始一定处于一个割点，每一步都会走进一个让 Jerry 活动范围更小的割点，从而 Jerry 被迫在一个更小的子连通块内走，最终被抓到。

考虑建出原图的圆方树，现在把 a 提起来当圆方树的根，设 b 在换根后的树上位于 a 的 b' 子树，则 b 一开始只能在 b' 子树内的圆点内活动。

现在 Tom 想要把当前位置 p 移到一个 q，满足：

这个几个条件同时也告诉我们 q 一定是 p 所在的某个点双的除 p 以外的点（称此为条件 P），这样才可能满足距离为 1。

注意到 Jerry 在第一次操作时可以在任何一个符合条件的点，所以 \forall u \in subtree_{b'}，都需要满足在按照上面的方式操作后，存在一种方案使得 Tom 最终 p = u。

也就是说，\forall p \in subtree_{b'} 且 q 满足条件 P，p, q 在原图上有边。

我们肯定不可能把每个 a 拿出来当根讨论，于是考虑换根 dp，预处理 f_u, g_u 表示以 1 为根时内 / 外子树是否满足上述条件，回答询问时讨论一下 b 是否在 a 的子树中即可。

但因为 a 一开始可能不是割点，一开始 Jerry 可以处在一个任意点。

注意到此时 Tom 并非必败，因为此时 Tom 还有另一种策略：

在换根 dp 结束后看一下有没有点 u 满足 f_u = g_u = \operatorname{true}，如果有则答案为全 Yes，否则该策略一定不可行。

综上，时间复杂度为 O(m + (n + q) \log n)。

代码：

#include <iostream>
#include <set>
#include <stack>
#include <cmath>

using namespace std;

typedef struct {
    int nxt;
    int end;
} Edge;

int cnt1 = 0, cnt2 = 0;
int head1[100007], dfn[100007], low[100007], head2[200007], depth[200007], in[200007], fa[200007][27], out[200007];
bool vis[100007], dp1[200007], dp2[200007];
Edge edge1[200007], edge2[400007];
set<int> se1;
stack<int> stk;
set<int> se2[100007];

inline void add_edge1(int start, int end){
    cnt1++;
    edge1[cnt1].nxt = head1[start];
    head1[start] = cnt1;
    edge1[cnt1].end = end;
}

inline void add_edge2(int start, int end){
    cnt2++;
    edge2[cnt2].nxt = head2[start];
    head2[start] = cnt2;
    edge2[cnt2].end = end;
}

void tarjan(int u, int father, int n, int &id, int &bcc_cnt){
    int son_cnt = 0;
    dfn[u] = low[u] = ++id;
    vis[u] = true;
    stk.push(u);
    for (register int i = head1[u]; i != 0; i = edge1[i].nxt){
        int x = edge1[i].end;
        if (!vis[x]){
            son_cnt++;
            tarjan(x, u, n, id, bcc_cnt);
            low[u] = min(low[u], low[x]);
            if (low[x] >= dfn[u]){
                int pos = ++bcc_cnt + n, cur;
                add_edge2(pos, u);
                add_edge2(u, pos);
                do {
                    cur = stk.top();
                    stk.pop();
                    add_edge2(pos, cur);
                    add_edge2(cur, pos);
                } while (cur != x);
            }
        } else {
            low[u] = min(low[u], dfn[x]);
        }
    }
    if (father == 0 && son_cnt == 0){
        int pos = ++bcc_cnt + n;
        add_edge2(pos, u);
        add_edge2(u, pos);
    }
}

void dfs1(int u, int father, int n, int &id){
    int t;
    depth[u] = depth[father] + 1;
    t = log2(depth[u]);
    in[u] = ++id;
    fa[u][0] = father;
    for (register int i = 1; i <= t; i++){
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    dp1[u] = true;
    for (register int i = head2[u]; i != 0; i = edge2[i].nxt){
        int x = edge2[i].end;
        if (x != father){
            dfs1(x, u, n, id);
            dp1[u] &= dp1[x];
            if (u > n) dp1[u] &= se2[father].count(x);
        }
    }
    out[u] = id;
}

void dfs2(int u, int n){
    int cnt1 = 0, size;
    se1.clear();
    if (fa[u][0] != 0) se1.insert(fa[u][0]);
    for (register int i = head2[u]; i != 0; i = edge2[i].nxt){
        int x = edge2[i].end;
        if (x != fa[u][0]){
            se1.insert(x);
            if (!dp1[x]) cnt1++;
        }
    }
    size = se1.size();
    for (register int i = head2[u]; i != 0; i = edge2[i].nxt){
        int x = edge2[i].end;
        if (x != fa[u][0]){
            dp2[x] = dp2[u] && (cnt1 == 0 || (cnt1 == 1 && !dp1[x]));
            if (u > n){
                int cnt2 = 0;
                for (register int j = head1[x]; j != 0; j = edge1[j].nxt){
                    if (se1.count(edge1[j].end)) cnt2++;
                }
                dp2[x] &= cnt2 + 1 == size;
            }
        }
    }
    for (register int i = head2[u]; i != 0; i = edge2[i].nxt){
        int x = edge2[i].end;
        if (x != fa[u][0]) dfs2(x, n);
    }
}

inline bool check(int u, int v){
    return in[u] <= in[v] && in[v] <= out[u];
}

inline int jump(int u, int k){
    for (register int i = 0; (1 << i) <= k; i++){
        if (k >> i & 1) u = fa[u][i];
    }
    return u;
}

int main(){
    int n, m, q, dfn_id1 = 0, bcc_cnt = 0, dfn_id2 = 0;
    cin >> n >> m >> q;
    for (register int i = 1; i <= m; i++){
        int x, y;
        cin >> x >> y;
        se2[x].insert(y);
        se2[y].insert(x);
        add_edge1(x, y);
        add_edge1(y, x);
    }
    tarjan(1, 0, n, dfn_id1, bcc_cnt);
    dfs1(1, 0, n, dfn_id2);
    dp2[1] = true;
    dfs2(1, n);
    for (register int i = 1; i <= n; i++){
        if (dp1[i] && dp2[i]){
            for (register int j = 1; j <= q; j++){
                cout << "Yes" << endl;
            }
            return 0;
        }
    }
    for (register int i = 1; i <= q; i++){
        int a, b;
        cin >> a >> b;
        if (!check(a, b)){
            if (dp2[a]){
                cout << "Yes" << endl;
            } else {
                cout << "No" << endl;
            }
        } else if (dp1[jump(b, depth[b] - depth[a] - 1)]){
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}