题目背景
自选题 by ix35
题目描述
给定一张包含 \(n\) 个顶点和 \(m\) 条边的 无向连通图，Tom 和 Jerry 在图上进行了 \(q\) 次追逐游戏。
在第 \(i\) 次游戏中，Tom 一开始位于顶点 \(a_i\)，而 Jerry 一开始位于顶点 \(b_i\)（双方任何时候都知道自己和对方的位置），追逐规则如下：
-
Jerry 和 Tom 交替行动，Jerry 先行动。
-
Jerry 每次行动可以通过无向图中的 任意多条边（可以选择不移动），但是在移动过程中不能经过 Tom 当前所在的结点，否则就会被抓住。
-
Tom 每次行动只能通过无向图中的 至多一条边（可以选择不移动）。
-
如果 Tom 在一次行动后到达了 Jerry 的位置，那么 Tom 胜利。
Tom 尽量想要胜利，而 Jerry 会尽量阻止 Tom 胜利。
现在你需要对于每一局游戏，求出 Tom 是否一定能在有限次行动内获胜。
对于 \(100\%\) 的数据，\(1\leq n,m,q\leq 10^5\)，\(1\leq x,y,a,b\leq n\)，\(a_i\ne b_i\)。
感性一下，会发现Tom 每一步一定是走在割点上的，不然的话 Jerry 一下子就会飞走。
那么找到圆方树，那么两个点 \((x,y)\) 称为好的，当且仅当在圆方树上他们的路径中任意两点是在原图相邻的。
而 Tom 在 \(x\)，Jerry 在 \(y\) 点时，如果 \(x\) 考 \(y\) 的那个连通块满足任意一个点 \(u\)，\((x,u)\) 是好的，Tom 就可以抓住 Jerry.
然后可以树形 dp 求出来某一棵子树是否满足根节点到自述中其他所有节点都是好的，换根 dp 求出来是否到子树外任意一点是好的。
如果有一个点满足到另外任意一个点都是好的，那么 Tom 可以先到这个店，所有询问都是 Yes.
否则就倍增出来看 Tom 在那棵子树，然后回答答案。
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m,f[N],p[N],c,fa[N][20],dfn[N],low[N],idx,st[N],tp,dep[N],in[N],q,x,y;
vector<int>g[N],h[N];
map<int,int>mp[N];
void tarjan(int x)
{
dfn[x]=low[x]=++idx;
st[++tp]=x;
for(int v:g[x])
{
if(!dfn[v])
{
tarjan(v);
low[x]=min(low[x],low[v]) ;
if(low[v]==dfn[x])
{
++c;
while(st[tp+1]^v)
{
h[c].push_back(st[tp]),h[st[tp]].push_back(c);
--tp;
}
h[c].push_back(x),h[x].push_back(c);
}
}
else
low[x]=min(low[x],dfn[v]);
}
}
void sou(int x,int y)
{
dep[x]=dep[y]+1;
fa[x][0]=y;
for(int i=1;i<=19;i++)
fa[x][i]=fa[fa[x][i-1]][i-1];
f[x]=1;
for(int v:h[x])
{
if(v==y)
continue;
sou(v,x);
if(x<=n)
f[x]&=f[v];
else
f[x]&=mp[y][v]&f[v];
}
}
int ask(int x,int k)
{
for(int i=0;i<20;i++)
if(k>>i&1)
x=fa[x][i];
return x;
}
void dfs(int x,int y)
{
int cnt=0;
p[x]=1;
for(int v:h[x])
if(v^y)
cnt+=f[v];
for(auto v:h[x])
if(v^y&&(x<=n||in[v]==h[x].size()-1)&&cnt-f[v]==h[x].size()-1-(bool)y)
dfs(v,x);
}
int main()
{
scanf("%d%d%d",&n,&m,&q),c=n;
for(int i=1,u,v;i<=m;i++)
{
scanf("%d%d",&u,&v),mp[u][v]=mp[v][u]=1;
g[u].push_back(v),g[v].push_back(u);
}
tarjan(1);
sou(1,0);
for(int i=1;i<=n;i++)
{
for(auto v:g[i])
{
if(v>i)
continue;
if(fa[i][1]==v)
in[i]++;
else if(fa[v][1]==i)
in[v]++;
else
in[i]++,in[v]++;
}
}
dfs(1,0);
for(int i=1;i<=n;i++)
{
if(f[i]&&p[i])
{
for(int j=1;j<=q;j++)
puts("Yes");
return 0;
}
}
while(q--)
{
scanf("%d%d",&x,&y);
if(dep[y]<dep[x]||ask(y,dep[y]-dep[x])^x)
puts(p[x]? "Yes":"No");
else
puts(f[ask(y,dep[y]-dep[x]-1)]? "Yes":"No");
}
}