题目链接：
H - Rescue the Princess
学习链接：
zoj4097 Rescue the Princess无向图缩点有重边+lca - lhc..._博客园
题目大意：
首先是T组测试样例，然后是n个点，m条双向边。然后给你u,v,w。问你v和w是否能够到达u，两个人走过的边不能有重复，否则这条边会被压塌。
具体思路：首先对能形成连通块的进行缩点，构成一个个的连通图。然后这样整个图就变成了一个森林，然后再根据染色后的连通块重新建图。
对于每一次的询问，先看这三个点是不是在同一个连通图里面，如果不是在一个连通图里面肯定是非法情况。
然后再就是讨论在同一个连通图里面的情况，通过讨论v和u的关系来表示出所有的情况。
情况1，lca(u,v)=u.
这种时候肯定是满足的，lca(u,v)=lca(u,w)=lca(v,w)=u.
情况2，lca（u，v）=v.
情况3，lca（u,v）!=u&&lca(u,v)!=v.
讨论上述情况就可以了。
AC代码：
#include<bits/stdc++.h>
using namespace std;
# define ll long long
const int maxn =2e5+;
int n,m,k,num,ordofblock,ordoftree;
vector<int>Edge1[maxn];
vector<int>Edge2[maxn];
int dfn[maxn],low[maxn];
int tree[maxn],block[maxn],vis[maxn];
int depth[maxn],father[maxn][];
stack<int>q;
void init()
{
for(int i=; i<=n; i++)
{
Edge1[i].clear();
Edge2[i].clear();
vis[i]=;
dfn[i]=;
low[i]=;
tree[i]=;
block[i]=;
depth[i]=;
for(int j=;j<=;j++)father[i][j]=;
}
while(!q.empty())
q.pop();
num=;
ordofblock=ordoftree=;
}
void tarjan(int cur,int fa,int ord)
{
tree[cur]=ord;
low[cur]=dfn[cur]=++num;
q.push(cur);
int flag=;
for(int i=; i<Edge1[cur].size(); i++)
{
int to=Edge1[cur][i];
if(to==fa)
{
if(++flag<)
continue;
}
if(!dfn[to])
{
tarjan(to,cur,ord);
low[cur]=min(low[cur],low[to]);
}
else if(!block[to])
{
low[cur]=min(low[cur],dfn[to]);
}
}
if(low[cur]==dfn[cur])
{
ordofblock++;
int tmp;
do
{
tmp=q.top();
q.pop();
block[tmp]=ordofblock;
}
while(tmp!=cur);
}
}
void dfs(int u,int root)
{
vis[u]=;
depth[u]=depth[root]+;
father[u][]=root;
for(int i=; (<<i)<=depth[u]; i++)
{
father[u][i]=father[father[u][i-]][i-];
}
for(int i=; i<Edge2[u].size(); i++)
{
int to=Edge2[u][i];
if(to==root)
continue;
dfs(to,u);
}
}
int lca(int t1,int t2)
{
if(depth[t1]>depth[t2])
swap(t1,t2);
for(int i=; i>=; i--)
{
if(depth[t1]<=depth[t2]-(<<i))
{
t2=father[t2][i];
}
}
if(t1==t2)
return t1;
for(int i=; i>=; i--)
{
if(father[t1][i]!=father[t2][i])
{
t1=father[t1][i];
t2=father[t2][i];
}
}
return father[t1][];
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d %d %d",&n,&m,&k);
init();
int st,ed;
for(int i=; i<=m; i++)
{
scanf("%d %d",&st,&ed);
Edge1[st].push_back(ed);
Edge1[ed].push_back(st);
}
for(int i=; i<=n; i++)
{
if(!dfn[i])
{
ordoftree++;
tarjan(i,,ordoftree);
}
}
for(int i=; i<=n; i++)
{
for(int j=; j<Edge1[i].size(); j++)
{
int to=Edge1[i][j];
if(block[i]!=block[to])
{
Edge2[block[i]].push_back(block[to]);
}
}
}
for(int i=; i<=ordofblock; i++)
{
if(!vis[i])
dfs(i,i);
}
int u,v,w;
for(int i=; i<=k; i++)
{
scanf("%d %d %d",&u,&v,&w);
if(tree[u]!=tree[v]||tree[u]!=tree[w]||tree[v]!=tree[w])
{
printf("No\n");
continue;
}
int flag=;
u=block[u],v=block[v],w=block[w];
int uv=lca(u,v);
int uw=lca(u,w);
int vw=lca(v,w);
if(uv==u){
if(uw==u&&vw==u)flag=;
else if(uw!=u)flag=;
else flag=;
}
else if(uv==v){
if(uw==u)flag=;
else flag=;
}
else {
if(uw!=u)flag=;
}
if(flag)
printf("Yes\n");
else
printf("No\n");
}
}
return ;
}