P7353 题解

· · 题解

观察题目得到若干抽象的胜利方式，基本上和"封路"以及"一步能到"有关，这样我们可以考虑两种方式：

  1. 存在一个点满足对所有点均胜利。

  2. 当前点（一般为割点）一定需要封住才可胜利。

这个分类非常重要，使得我们仅需考虑当前点是否能封住的问题，弱化了条件。

先考虑 2，如何使当前点封住？不难发现，对于一个点双而言，如果 Tom 在当前点到不了点双内的所有点，那么一定封不住（先取到到不了的点，等 Tom 移动时跑出），其他的点双也一样。

而 Tom 需要干的是每次到达一个新的割点，将 Jerry 封在一个新的条件中。有点像状态转移。可以在圆方树上进行 dp。结合换根和一定的细节即可完成这个题目。时间复杂度为 \mathcal O(m \log m)。

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define per(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
const int N=2e5+5;
int n,m,q,idx,ds,dfn[N],low[N],f[N][20],dep[N],dp[N],dp1[N];
map<int,int> mp[N],in[N];
stack<int> st;
vector<int> v[N],d[N],e[N];
void tj(int x,int fa){
    dfn[x]=low[x]=++idx,st.push(x);
    for(auto dq:v[x]) if(dq!=fa){
        if(!dfn[dq]){
            tj(dq,x),low[x]=min(low[x],low[dq]);
            if(low[dq]>=dfn[x]){
                ds++,e[ds].push_back(x),e[x].push_back(ds);
                for(auto d1:d[x]) in[ds][d1]++,in[ds][x]++;
                d[x].clear();
                while(1){
                    int d1=st.top(); st.pop(),e[ds].push_back(d1),e[d1].push_back(ds);
                    for(auto d2:d[d1]) in[ds][d2]++,in[ds][d1]++;
                    d[d1].clear(); if(d1==dq) break;
                }
            }
        }else d[dq].push_back(x),low[x]=min(low[x],dfn[dq]);
    }else d[dq].push_back(x);
}
int lca(int x,int y){
    if(dep[x]>dep[y]) swap(x,y);
    per(i,19,0) if(dep[f[y][i]]>=dep[x]) y=f[y][i];
    if(x==y) return x;
    per(i,19,0) if(f[y][i]!=f[x][i]) y=f[y][i],x=f[x][i];
    return f[x][0];
}
void dfs(int x,int fa){
    dep[x]=dep[fa]+1,f[x][0]=fa,dp[x]=1;
    rep(i,1,19) f[x][i]=f[f[x][i-1]][i-1];
    for(auto dq:e[x]) if(dq!=fa){
        dfs(dq,x),dp[x]&=dp[dq];
        if(x>n&&mp[fa].find(dq)==mp[fa].end()) dp[x]=0;
    }
}
void dfs1(int x,int fa){
    int cnt=0;
    for(auto dq:e[x]) if(dq!=fa) cnt+=(!dp[dq]);
    if(x>n) for(auto dq:e[x]) if(dq!=fa) if(cnt-(!dp[dq])==0&&in[x][dq]==e[x].size()-1) dp1[dq]=dp1[x];
    else for(auto dq:e[x]) if(dq!=fa) if(cnt-(!dp[dq])==0) dp1[dq]=dp1[x];
    for(auto dq:e[x]) if(dq!=fa) dp1[dq]&=dp1[x];
    for(auto dq:e[x]) if(dq!=fa) dfs1(dq,x);
}
signed main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>q,ds=n;
    rep(i,1,m){int u,vv; cin>>u>>vv,mp[u][vv]=mp[vv][u]=1,v[u].push_back(vv),v[vv].push_back(u);}
    tj(1,0),dfs(1,0),dp1[1]=1,dfs1(1,0); int pd=0;
    rep(i,1,ds) if(dp[i]&&dp1[i]) pd=1;
    while(q--){
        int u,vv,lc; cin>>u>>vv,lc=lca(u,vv);
        if(pd){cout<<"Yes\n"; continue;}
        if(u!=lc) cout<<(dp1[u]?"Yes\n":"No\n");
        else{
            per(i,19,0) if(dep[f[vv][i]]>dep[lc]) vv=f[vv][i];
            cout<<(dp[vv]?"Yes\n":"No\n");
        }
    }
}