P3854 题解
llxsmy_forever
·
·
题解
看到题解大多是用圆方树做的，圆方树是什么，于是蒟蒻来发一篇用点双的题解。
题目描述
给定一张无向连通图，多组询问，每组询问给出点 X,Y,D ，在删除点 D 之后，判断点 X,Y 是否连通。
Solution
对于每组询问，我们分情况讨论。
$\bullet$ 如果点 $X$ 和 $Y$ 处于同一个点双之内，那么不管删除哪一个点， $X$ 和 $Y$ 显然还是联通的，输出 no。
$\bullet$ 最后一种情况，就是 $X$ 和 $Y$ 不在同一个点双之内并且 $D$ 点是割点，这时我们先缩点，此时这张图变成一棵树，设 $tx$ 为 $X$ 所在的点双，$ty$ 为 $Y$ 所在的点双，我们只需判断 $D$ 点是否在 $tx$ 到 $ty$ 的路径上就可以了，在则输出 yes，否则输出 no。
如何判断树上的一个点 $D$ 是否在另两个点 $X$ 和 $Y$ 的路径上呢，我们只需要判断 $dist(X,D)$ 加上 $dist(Y,D)$ 是否等于 $dist(X,Y)$ 就可以了。
## Code
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=2e4+100,M=1e5+100;
struct edge{int y,pre;}a[M<<1];int alen,last[N];
void ins(int x,int y){alen++;a[alen]={y,last[x]};last[x]=alen;}
int dfn[N],low[N],id,dcc;
int sta[N],top,vis[N],New[N],c[N];
vector<int> q[N];
void tarjan(int x){
dfn[x]=low[x]=++id;
sta[++top]=x;
int cnt=0;
for(int k=last[x];k;k=a[k].pre){
int y=a[k].y;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
if(dfn[x]<=low[y]){
cnt++;
if(x>1||cnt>1)vis[x]=1;
int tmp;dcc++;
do{
tmp=sta[top--];
q[dcc].push_back(tmp);
}while(tmp!=y);
q[dcc].push_back(x);
}
}
else low[x]=min(low[x],dfn[y]);
}
}
int dep[N],par[N][21];
void prepare(int x,int fa){
dep[x]=dep[fa]+1;par[x][0]=fa;
for(int i=1;i<=19;i++)par[x][i]=par[par[x][i-1]][i-1];
for(int k=last[x];k;k=a[k].pre){
int y=a[k].y;
if(y!=fa)prepare(y,x);
}
}
int LCA(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=19;i>=0;i--){
if(dep[par[x][i]]>=dep[y])x=par[x][i];
}
if(x==y)return y;
for(int i=19;i>=0;i--){
if(par[x][i]!=par[y][i]){
x=par[x][i],y=par[y][i];
}
}
return par[x][0];
}
int dist(int x,int y,int lca){
return dep[x]+dep[y]-dep[lca]*2;
}
int main(){
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int x,y;scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);
}
tarjan(1);
int sum=dcc;
for(int i=1;i<=n;i++){
if(vis[i])New[i]=++sum;
}
alen=0;memset(last,0,sizeof(last));
for(int i=1;i<=dcc;i++){
for(int j=0;j<q[i].size();j++){
int x=q[i][j];
if(vis[x])ins(New[x],i),ins(i,New[x]);
else c[x]=i;
}
}
prepare(1,0);
int q;scanf("%d",&q);
while(q--){
int x,y,d;scanf("%d%d%d",&x,&y,&d);
x=vis[x]?New[x]:c[x];
y=vis[y]?New[y]:c[y];
if(x==y||!vis[d]){
puts("no");
continue;
}
d=New[d];
int lca1=LCA(x,y),lca2=LCA(x,d),lca3=LCA(y,d);
if(dist(x,y,lca1)==dist(x,d,lca2)+dist(y,d,lca3))puts("yes");
else puts("no");
}
return 0;
}
```