[2020-2021 集训队作业] Tom & Jerry
_ANIG_
·
·
题解
传送门
首先考虑两人的策略是什么。
Jerry 的行动较为复杂，不好考虑策略。
Tom 行动比较简单，不妨从 Tom 的策略入手。
整体感受一下，Tom 为了抓住 Jerry，所以会朝着 Jerry 的方向一直走。
建出圆方树，在树上考虑。
若 Tom 当前能走到一个距离 Jerry 更近的点，则一定往这个方向走，否则，Tom 在不会远离 Jerry 的前提下走向度数最大的点，这是为了处理 Jerry 始终与 Tom 距离为 1 的情况。
所以可以让 Tom 使用如下策略：若可以接近 Jerry，则往 Jerry 的方向走。否则走向不会远离 Jerry 的度数最大的点。
考虑图论建模，用点 (a,b) 表示 Tom 在 a，Jerry 在 b，轮到 Jerry 这个状态。
在新图上跑 SCC，则 Tom 能赢的充要条件为当前状态无法到达一个大小大于 $1$ 的 SCC。
可以发现，很多状态是可以合并的。
由于 Jerry 可以走任意步，所以不妨设 $(x,y)$ 表示 Tom 在 $x$，Jerry 可以到达以 $x$ 为根时 $y$ 的子树内的任意点。
此时总点数为 $O(n)$，边数 $O(n^2)$，但很难卡满。
瓶颈在于给一个点除掉一个儿子后的其他儿子连边。
可以使用经典技巧，新建虚点表示给前后缀连边，这样边数 $O(n)$，总复杂度 $O((n+q)\log n)$。
使用哈希表和长剖求 k 级祖先等精细实现可能可以做到 $O(n+q)$。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,qs,dfn[N],dd[N],rd[N],f[N],siz[N],bh[N],sms,cnt,low[N],eds[N],idx,tot,fa[N][20],mk[N],dep[N];
vector<int>e[N],st,p[N],g[N],b[N],to[N];
unordered_map<int,int>dy[N],wz[N],dds[N];
vector<int>qz[N],hz[N];
deque<int>q;
void tarjan(int x){
st.push_back(x);
dfn[x]=low[x]=++idx;
for(auto c:e[x]){
if(!dfn[c]){
tarjan(c);
low[x]=min(low[x],low[c]);
if(dfn[x]<=low[c]){
int y;cnt++;
do{
y=st.back();
st.pop_back();
p[cnt].push_back(y);
p[y].push_back(cnt);
}while(y!=c);
p[cnt].push_back(x);
p[x].push_back(cnt);
}
}else low[x]=min(low[x],dfn[c]);
}
}
void dfs1(int x){
mk[x]=1;dfn[x]=++idx;
for(int i=1;i<=19;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
for(auto c:p[x]){
if(mk[c])continue;
fa[c][0]=x;
dep[c]=dep[x]+1;
dfs1(c);
}
eds[x]=idx;
mk[x]=0;
}
void dfs2(int x){
dd[x]=low[x]=++idx;
st.push_back(x);
mk[x]=1;
for(auto c:b[x]){
if(!dd[c]){
dfs2(c);
low[x]=min(low[x],low[c]);
}else if(mk[c])low[x]=min(low[x],dd[c]);
}
if(dd[x]==low[x]){
int y;sms++;
do{
y=st.back();
st.pop_back();
bh[y]=sms;mk[y]=0;
siz[sms]++;
}while(y!=x);
}
}
int gm(int a,int b){
if(fa[a][0]==fa[b][0])return fa[a][0];
if(fa[a][1]==b)return fa[a][0];
return fa[b][0];
}
int up(int x,int k){
while(k){
x=fa[x][__lg(k&-k)];
k^=k&-k;
}
return x;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m>>qs;
cnt=n;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
e[x].push_back(y);
e[y].push_back(x);
}
tarjan(1);
for(int i=1;i<=n;i++){
for(auto c:p[i])dy[i][c]=++tot;
qz[i].resize(p[i].size());
hz[i].resize(p[i].size());
for(int j=0;j<p[i].size();j++){
int c=p[i][j];
wz[i][c]=j;
qz[i][j]=++tot;
hz[i][j]=++tot;
if(j)b[qz[i][j]].push_back(qz[i][j-1]);
b[qz[i][j]].push_back(dy[i][c]);
b[hz[i][j]].push_back(dy[i][c]);
}
for(int j=0;j+1<p[i].size();j++)b[hz[i][j]].push_back(hz[i][j+1]);
}
idx=0;
dfs1(1);
for(int i=1;i<=n;i++){
for(auto c:e[i]){
int tmp=gm(i,c);
dds[i][tmp]++;
}
}
for(int i=1;i<=n;i++){
for(auto c:e[i]){
int tmp=gm(i,c);
g[tmp].push_back(c);
}
for(auto c:p[i]){
sort(g[c].begin(),g[c].end(),[&](int a,int b){
return dds[a][c]>dds[b][c];
});
int tmp=dy[i][c];
for(auto d:g[c]){
int k=wz[d][c];
if(k)b[tmp].push_back(qz[d][k-1]);
if(k+1<p[d].size())b[tmp].push_back(hz[d][k+1]);
}
if(g[c].size()<p[c].size()-1){
b[tmp].push_back(dy[g[c][0]][c]);
}
g[c].clear();
}
}
idx=0;
for(int i=1;i<=tot;i++)if(!dd[i])dfs2(i);
for(int i=1;i<=tot;i++){
for(auto c:b[i]){
if(bh[i]==bh[c])continue;
to[bh[c]].push_back(bh[i]);
rd[bh[i]]++;
}
if(siz[i]>1)f[i]=1;
}
for(int i=1;i<=tot;i++)if(!rd[i])q.push_back(i);
while(q.size()){
int x=q.front();
q.pop_front();
for(auto c:to[x]){
rd[c]--;
f[c]|=f[x];
if(!rd[c])q.push_back(c);
}
}
while(qs--){
int a,b;
cin>>a>>b;
if(dfn[b]>=dfn[a]&&dfn[b]<=eds[a]){
b=up(b,dep[b]-dep[a]-1);
}else{
b=fa[a][0];
}
if(f[bh[dy[a][b]]])cout<<"No\n";
else cout<<"Yes\n";
}
}
```