题目链接：ZOJ4097-Rescue the Princess

题意：

给一个图(不保证连通)，然后给q个询问，每次询问为给三个点u，v，w，然后问是否存在两条路径可以分别使v到u和w到u，并且这两条路径不能有重合。

题解：

考场上想到了tarjan求桥之后缩点然后做LCA，但无奈当时只会离线的LCA。。。

首先用tarjan进行边双缩点，然后对于每个询问，以u为根判断v和w的LCA是不是u即可。

关于具体操作，因为每次建树的话复杂度要爆炸，所以单对每一个连通块建树，然后对于每次询问的时候，同时把u，LCA(u，v)，LCA(u，w)，LCA(v，w)四个点放入数组中进行排序，若最后两个都为u的话，即在以u为根的树中，LCA(v，w)=u。(神仙操作)

参考代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 9;
const int MAXM = 2e5 + 9;
int T, n, m, q, N;
int tot = 0, sig = 0, blockcnt = 0;
int dfn[MAXN], low[MAXN], father[MAXN], col[MAXN], block[MAXN], depth[MAXN];
int grand[MAXN][30];
stack<int> S;
vector<int> newedge[MAXN];
bool used[MAXM * 2], vis[MAXN];
struct EDGE
{
    int v, nxt, lca;
} edge1[MAXM * 2], qedge[5];
int ecnt1 = 0, fir1[MAXN];
void addedge_1(int u, int v)
{
    edge1[ecnt1].v = v;
    edge1[ecnt1].nxt = fir1[u];
    fir1[u] = ecnt1++;
}
void tarjan(int u, int Father)
{
    tot++;
    dfn[u] = low[u] = tot;
    S.push(u);
    vis[u] = 1;
    father[u] = Father;
    for (int i = fir1[u]; i != -1; i = edge1[i].nxt)
    {
        if (used[i] == 0)
        {
            used[i] = used[i ^ 1] = 1;
            int v = edge1[i].v;
            if (!dfn[v])
            {
                tarjan(v, u);
                low[u] = min(low[u], low[v]);
            }
            else//考虑重边
                low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u])
    {
        sig++;
        while (1)
        {
            int temp = S.top();
            S.pop();
            vis[temp] = 0;
            col[temp] = sig;
            if (temp == u)
                break;
        }
    }
}
void getblock(int u)
{
    block[u] = blockcnt;
    for (int i = fir1[u]; i != -1; i = edge1[i].nxt)
    {
        int v = edge1[i].v;
        if (!block[v])
            getblock(v);
    }
}
void dfs(int u)
{
    vis[u] = 1;
    for (int i = 1; i <= N; i++)
        grand[u][i] = grand[grand[u][i - 1]][i - 1];
    for (int i = 0; i < newedge[u].size(); i++)
    {
        int v = newedge[u][i];
        if (v != grand[u][0])
        {
            depth[v] = depth[u] + 1;
            grand[v][0] = u;
            dfs(v);
        }
    }
}
int lca(int x, int y)
{
    if (x == y)
        return x;
    if (depth[x] > depth[y])
        swap(x, y);
    for (int i = N; i >= 0; i--)
        if (depth[x] < depth[y] && depth[x] <= depth[grand[y][i]])
            y = grand[y][i];
    if (x == y)
        return x;
    for (int i = N; i >= 0; i--)
        if (grand[x][i] != grand[y][i])
            x = grand[x][i], y = grand[y][i];
    if (grand[x][0] == 0 && grand[y][0] == 0 && x != y)
        return -1;
    return grand[x][0];
}
int main()
{
    // freopen("in.dat", "r", stdin);
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d%d", &n, &m, &q);
        memset(col, 0, sizeof(col));
        memset(dfn, 0, sizeof(dfn));
        memset(low, 0, sizeof(low));
        memset(vis, 0, sizeof(vis));
        memset(used, 0, sizeof(used));
        memset(fir1, -1, sizeof(fir1));
        memset(block, 0, sizeof(block));
        memset(depth, 0, sizeof(depth));
        memset(father, 0, sizeof(father));
        ecnt1 = tot = sig = blockcnt = 0;
        while (!S.empty())
            S.pop();
        for (int i = 1; i <= m; i++)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            if (u == v)
                continue;
            addedge_1(u, v), addedge_1(v, u);
        }
        for (int i = 1; i <= n; i++)
            if (!block[i])
            {
                blockcnt++;
                getblock(i);
            }
        for (int i = 1; i <= n; i++)
            if (!dfn[i])
                tarjan(i, i);
        for (int i = 1; i <= sig; i++)
            newedge[i].clear();
        for (int u = 1; u <= n; u++)
            for (int i = fir1[u]; i != -1; i = edge1[i].nxt)
            {
                int v = edge1[i].v;
                if (col[u] != col[v])
                    newedge[col[u]].push_back(col[v]);
            }
        memset(vis, 0, sizeof(vis));
        depth[0] = -1;
        N = floor(log(sig + 0.0) / log(2.0)) + 1;
        for (int i = 1; i <= sig; i++)
        {
            if (!vis[i])
            {
                depth[i] = 0;
                dfs(i);
            }
        }
        while (q--)
        {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            if (block[x] != block[y] || block[x] != block[z])
            {
                puts("No");
                continue;
            }
            x = col[x], y = col[y], z = col[z];
            if (x == y || x == z)
            {
                puts("Yes");
                continue;
            }
            if (y == z)
            {
                puts("No");
                continue;
            }
            int t[] = {x, lca(x, y), lca(x, z), lca(y, z)};
            sort(t, t + 4, [](int x0, int y0) { return depth[x0] < depth[y0]; });
            if (t[2] == x && t[3] == x)
                puts("Yes");
            else
                puts("No");
        }
    }
    return 0;
}