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

· · 题解

ix35 论文《综述图论中连通性及相关问题的一些处理方法》中的一道题。

注意到点双有一个良好的性质：在点双中，从任意一点能够不经过指定点到达另一点。这个性质保证了 Jerry 能够在点双中任意行走，也提示我们用点双的角度思考问题。

考虑建出圆方树，假设 Tom 所在的结点 a 为根。如果 Tom 能够沿着圆方树中 a\to b 的路径一直走下去，必然是能够捉住 Jerry 的。否则，它一定会走到路径中的一个分支结点，给 Jerry 溜走的机会。

用形式化的语言来描述它：设 (x,y) 是好的当前仅当圆方树 x\to y 的路径中任意两个相邻的圆点在原图中是相邻的。那么上述的获胜条件可以表示为：对于删掉点 a 后 b 所在连通块中的任意一点 x，都有 (a,x) 是好的。

不过，如果能够 找到一个点 u，对于任意一个点 x，(u,x) 都是好的 话，那么 Tom 也可以移至 u 所在点，然后类似的捉住 Jerry。

这两个就是全部的获胜条件了吗？确实是的，下面我们考虑证明必要性。如果两个条件均不满足，那么 Tom 必然会走到一个分支结点 p，此时必然存在一个点 q 满足 (p,q) 不是好的，此时 Jerry 可以跑到 q。但如果 p 在 b\to q 的必经之路上怎么办？那就在 Tom 到达 p 点之前到达 q 即可。既然 (p,q) 不是好的，那么 (a,q) 当然也不是好的。只要 Jerry 一直有机会停在不好的点上，那 Tom 就永远追不上 Jerry。

考虑用 DP 来判断这两个条件的可行性。设 f(x) 表示它（圆点）或它的父亲（方点）到子树中所有点是否都是好的，g(x) 表示它（圆点）到父亲所在那棵子树中所有点是否都是好的。这就是一个换根 DP。

对于 f(x)，显然有

对于 g(x)，考虑从父亲结点递推过来。由于 g(x) 只在圆点有定义，所以它的父亲必然是方点。g(x)=1 当且仅当以下条件全部满足：

事实上，第二个条件只需要满足这个点在该点双中的度数等于节点数减一即可，因为原图是无重边和自环的。

那么两个获胜规则的判定就很简单了，第二个就是能够找到一个点 x 使得 f(x)=g(x)=1。第一个简单分类讨论一下：如果 b 在 a 的父亲子树，就需要 g(a)=1；否则，就需要找到 b 在 a 的哪棵子树中，看它的 f 值是否等于一。

时间复杂度 O(n\log n)，默认 n,m,q 同阶。

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=2e5;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

struct Node{int frm,to,nxt;} Edge[Maxn*2+5];
int tot=1,Head[Maxn+5];
inline void Addedge(int x,int y) {Edge[++tot]=(Node){x,y,Head[x]},Head[x]=tot;}

int n,m,q,dfn[Maxn+5],low[Maxn+5],st[Maxn+5],top,cur,tmp;
int dep[Maxn+5],f[Maxn+5],g[Maxn+5],anc[Maxn+5][20],cnt[Maxn+5];
vector<int> v[Maxn+5];
vector<pair<int,int>> w[Maxn+5];
map<int,int> mp[Maxn+5];

inline int Get(int x,int y) {return dep[x]>dep[y]?anc[x][0]:anc[y][0];}
inline int LCA(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    Rof(i,19,0) if(dep[anc[x][i]]>=dep[y]) x=anc[x][i];
    if(x==y) return x;
    Rof(i,19,0) if(anc[x][i]==anc[y][i]) x=anc[x][i],y=anc[y][i];
    return anc[x][0];
}
inline int Jump(int x,int y) {Rof(i,19,0) if(y&(1<<i)) x=anc[x][i]; return x;}
inline void dfs(int x,int fa)
{
    dep[x]=dep[fa]+1,f[x]=1,anc[x][0]=fa;
    For(i,1,19) anc[x][i]=anc[anc[x][i-1]][i-1];
    if(x<=n) {for(auto y:v[x]) if(y!=fa) dfs(y,x),f[x]&=f[y];}
    else
    {
        for(auto y:v[x]) if(y!=fa)
        {
            dfs(y,x),f[x]&=f[y];
            if(mp[fa].find(y)==mp[fa].end()) f[x]=0;
        }
    }
}
inline void dfs2(int x,int fa)
{
    if(!g[x]) {for(auto y:v[x]) if(y!=fa) g[y]=0,dfs2(y,x); return;}
    if(x<=n)
    {
        int pre=1; for(auto y:v[x]) if(y!=fa) g[y]&=pre,pre&=f[y];
        reverse(v[x].begin(),v[x].end()),pre=1;
        for(auto y:v[x]) if(y!=fa) g[y]&=pre,pre&=f[y];
        reverse(v[x].begin(),v[x].end());
        for(auto y:v[x]) if(y!=fa) dfs2(y,x);
        return;
    }
    int ch=0,now=0;
    for(auto y:v[x]) if(y!=fa) ch++,now+=f[y],cnt[y]=0;
    for(auto i:w[x]) cnt[i.first]++,cnt[i.second]++;
    for(auto y:v[x]) if(cnt[y]==ch && now-f[y]==ch-1) g[y]=1;
    for(auto y:v[x]) if(y!=fa) dfs2(y,x);
}
inline void Tarjan(int x)
{
    dfn[x]=low[x]=++cur,st[++top]=x;
    for(int i=Head[x];i;i=Edge[i].nxt)
    {
        int y=Edge[i].to;
        if(!dfn[y])
        {
            Tarjan(y),low[x]=min(low[x],low[y]);
            if(low[y]==dfn[x])
            {
                v[x].push_back(++tmp),v[tmp].push_back(x);
                while(1)
                {
                    int k=st[top--]; v[k].push_back(tmp),v[tmp].push_back(k);
                    if(y==k) break;
                }
            }
        }
        else low[x]=min(low[x],dfn[y]);
    }
}

int main()
{
    n=read(),m=read(),q=read(),tmp=n;
    For(i,1,m)
    {
        int a=read(),b=read();
        Addedge(a,b),Addedge(b,a);
        mp[a][b]=mp[b][a]=1;
    }
    Tarjan(1),dfs(1,0);
    For(i,1,m)
    {
        int a=Edge[i*2].frm,b=Edge[i*2].to;
        w[Get(a,b)].emplace_back(a,b);
    }
    g[1]=1,dfs2(1,0);
    For(i,1,n) if(f[i] && g[i]) {while(q--) printf("Yes\n"); return 0;}
    while(q--)
    {
        int a=read(),b=read(),l=LCA(a,b);
        if(l!=a) printf("%s\n",g[a]?"Yes":"No");
        else l=Jump(b,dep[b]-dep[a]-1),printf("%s\n",f[l]?"Yes":"No");
    }
    return 0;
}