题意:给一个图,每次询问给三个点a,b,c,问是否存在一条从a到c,一条b到c的路径除c外无交点。
双连通分量缩点建出圆方树是必须的,然后我们需要判断c是否在a到b的路径上,或者c的某个相邻的方点(新建的节点)在a到b的路径上。最后这玩意判了很久就是一直不对,去膜了ccz代码……哦,lca(a,b),lca(a,c),lca(b,c)只有俩不同取值,异或一下就得到多余的一个,然后就很好判了。
#include<cstdio>
#include<algorithm>
#define MN 3100001
using namespace std; int read_p,read_ca;
inline int read(){
read_p=;read_ca=getchar();
while (read_ca<''||read_ca>'') read_ca=getchar();
while (read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();
return read_p;
}
struct na{int y,ne;}b[MN<<],B[MN<<];
int n,m,q,l[MN],num=,fa[MN],lo[MN],df[MN],F[MN][],de[MN],x,y,z,nm=,st[MN],top=,SSS=,L[MN],NUM=,ID=;
inline int min(int a,int b){return a<b?a:b;}
inline void in(int x,int y){b[++num].y=y;b[num].ne=l[x];l[x]=num;}
inline void IN(int x,int y){B[++NUM].y=y;B[NUM].ne=L[x];L[x]=NUM;}
void dfs(int x,int f){
fa[x]=ID;
df[x]=lo[x]=++nm;
for (int i=l[x];i;i=b[i].ne)
if (b[i].y!=f){
if (!df[b[i].y]){
st[++top]=b[i].y;
dfs(b[i].y,x);
lo[x]=min(lo[x],lo[b[i].y]);
if (lo[b[i].y]==df[x]) for (++SSS,IN(x,SSS);top&&df[st[top]]>=df[b[i].y];top--) IN(SSS,st[top]);
else if (lo[b[i].y]>df[x]) IN(x,b[i].y),top--;
}else lo[x]=min(lo[x],df[b[i].y]);
}
}
void work(int x){
df[x]=;
for (int i=;i<;i++) F[x][i]=F[F[x][i-]][i-];
for (int i=L[x];i;i=B[i].ne) de[B[i].y]=de[x]+,F[B[i].y][]=x,work(B[i].y);
}
inline int lca(int x,int y){
if (de[x]>de[y]) swap(x,y);
for (int i=;i>=;i--)
if (de[F[y][i]]>=de[x]) y=F[y][i];
if (x==y) return x;
for (int i=;i>=;i--)
if (F[x][i]!=F[y][i]) x=F[x][i],y=F[y][i];
return F[x][];
}
int main(){
n=read();m=read();q=read();SSS=n;
for (int i=;i<=m;i++) x=read(),y=read(),in(x,y),in(y,x);
for (int i=;i<=n;i++) if (!df[i]) ++ID,dfs(i,);
for (int i=;i<=n;i++) if (df[i]) de[i]=,work(i);
while(q--){
x=read();y=read();z=read();
if (fa[x]!=fa[z]||fa[y]!=fa[z])puts("NO");else
m=lca(x,y)^lca(y,z)^lca(x,z),puts(((m>n&&(m==F[z][]||F[m][]==z))||m==z)?"YES":"NO");
}
}