P4334 [COI 2007] Policija 题解

hzoi_Shadow · 2025-03-22 17:02:59 · 题解

题目传送门

前置知识

圆方树

解法

考虑广义圆方树。

建出广义圆方树后第二问是容易处理的。将限制条件转化为 a \to b 是否经过 c，即 c 在 \operatorname{LCA}(a,b) 的子树内且 a 或 b 在 c 的子树内。可以通过 DFS 序判断。

第一问由经典结论转化为 a \to b 是否经过 (c,d) 所在的点双的方点 e 且 (c,d) 是割边。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
struct node
{
    int nxt,to;
}e[1000010];
int head[100010],dfn[200010],low[100010],fa[200010],siz[200010],son[200010],top[200010],dep[200010],out[200010],du[200010],cnt=0,v_dcc=0,tot=0;
vector<int>g[200010];
stack<int>s;
void add(int u,int v)
{
    cnt++;  e[cnt]=(node){head[u],v}; head[u]=cnt;
}
void tarjan(int x)
{
    tot++;  dfn[x]=low[x]=tot;
    s.push(x);
    for(int i=head[x];i!=0;i=e[i].nxt)
    {
        if(dfn[e[i].to]==0)
        {
            tarjan(e[i].to);
            low[x]=min(low[x],low[e[i].to]);
            if(low[e[i].to]==dfn[x])
            {
                v_dcc++;
                g[v_dcc].push_back(x);  g[x].push_back(v_dcc);
                du[x]++;  du[v_dcc]++;
                int tmp=0;
                while(e[i].to!=tmp)
                {
                    tmp=s.top();  s.pop();
                    g[v_dcc].push_back(tmp);  g[tmp].push_back(v_dcc);
                    du[tmp]++;  du[v_dcc]++;
                }
            }
        }
        else  low[x]=min(low[x],dfn[e[i].to]);
    }
}
void dfs1(int x,int father)
{
    siz[x]=1;
    fa[x]=father;
    dep[x]=dep[father]+1;
    for(int i=0;i<g[x].size();i++)
    {
        if(g[x][i]!=father)
        {
            dfs1(g[x][i],x);
            siz[x]+=siz[g[x][i]];
            son[x]=(siz[g[x][i]]>siz[son[x]])?g[x][i]:son[x];
        }
    }
}
void dfs2(int x,int id)
{
    tot++;  dfn[x]=tot;
    top[x]=id;
    if(son[x]!=0)
    {
        dfs2(son[x],id);
        for(int i=0;i<g[x].size();i++)  if(g[x][i]!=fa[x]&&g[x][i]!=son[x])  dfs2(g[x][i],g[x][i]);
    }
    out[x]=tot;
}
int lca(int u,int v)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]>dep[top[v]])  u=fa[top[u]];
        else  v=fa[top[v]];
    }
    return dep[u]<dep[v]?u:v;
}
bool check(int x,int y)
{
    return dfn[x]<=dfn[y]&&dfn[y]<=out[x];
}
int main()
{
// #define Isaac
#ifdef Isaac
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    int n,m,q,pd,u,v,x,y,rt,tmp,i;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>u>>v;
        add(u,v);  add(v,u);
    }
    v_dcc=n;
    for(i=1;i<=n;i++)  if(dfn[i]==0)  tarjan(i);
    tot=0;  dfs1(1,0);  dfs2(1,1);
    cin>>q;
    for(i=1;i<=q;i++)
    {
        cin>>pd>>u>>v>>x;
        if(pd==1)
        {
            cin>>y;  if(dep[x]>dep[y])  swap(x,y);
            tmp=fa[y];  rt=lca(u,v);
            cout<<(du[tmp]==2&&(check(rt,tmp)&&(check(tmp,u)||check(tmp,v)))?"no":"yes")<<endl;
        }
        else
        {
            rt=lca(u,v);
            cout<<((check(rt,x)&&(check(x,u)||check(x,v)))?"no":"yes")<<endl;
        }
    }
    return 0;
}