bzoj 5165: 树上倍增

题意：

给你一颗树，询问若干个点的LCA。$n \le 3000000$

题解：

因为$n$很大，所以不能带$log$。有个结论，多个点的LCA就是dfs序最小的点和最大的点的LCA。然后tarjan就好了。

#include <bits/stdc++.h>
using namespace std;

const int inf = 0x3f3f3f3f;
bool v[3000010];
int n, num = 0, fst[3000010], fstq[3000010], q[1010][1010], nn1 = 1, nn2 = 0, id[3000010], f[3000010], ans[1010];
struct edge
{
    int x, y, n, id;
} e[3001010];

int fd(int x) { return f[x] == x ? x : f[x] = fd(f[x]); }
void ins(int x, int y)
{
    e[++num] = {x, y, fst[x], 0};
    fst[x] = num;
}
void insq(int x, int y, int id)
{
    e[++num] = {x, y, fstq[x], id};
    fstq[x] = num;
}
void dfs1(int x)
{
    id[x] = ++nn1;
    for (int i = fst[x]; i; i = e[i].n)
    {
        int y = e[i].y;
        dfs1(y);
    }
}
void dfs2(int x)
{
    v[x] = 1;
    for (int i = fst[x]; i; i = e[i].n)
    {
        int y = e[i].y;
        dfs2(y);
        f[y] = x;
    }
    for (int i = fstq[x]; i; i = e[i].n)
    {
        int y = e[i].y;
        if (v[y] && !ans[e[i].id])
            ans[e[i].id] = fd(y);
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        char op[3];
        scanf("%s", op);
        if (op[0] == 'A')
        {
            int x;
            scanf("%d", &x);
            ins(x, ++nn1);
        }
        else
        {
            nn2++;
            scanf("%d", &q[nn2][0]);
            for (int j = 1; j <= q[nn2][0]; j++)
                scanf("%d", &q[nn2][j]);
        }
    }
    nn1 = 0;
    dfs1(1);/*
    for (int i = 1; i <= nn1; i++)
        printf("%d ", id[i]);
    puts("");*/
    for (int i = 1; i <= nn2; i++)
    {
        int mn = inf, mx = 0, mnid, mxid;
        for (int j = 1; j <= q[i][0]; j++)
        {
            if (id[q[i][j]] < mn) mn = id[q[i][j]], mnid = q[i][j];
            if (id[q[i][j]] > mx) mx = id[q[i][j]], mxid = q[i][j];
        }
        // printf("%d %d\n", mnid, mxid);
        insq(mnid, mxid, i);
        insq(mxid, mnid, i);
    }
    for (int i = 1; i <= nn1; i++)
        f[i] = i;
    dfs2(1);/*
    for (int i = 1; i <= nn1; i++)
        printf("%d ", fd(i));
    puts("");*/
    for (int i = 1; i <= nn2; i++)
        printf("%d\n", ans[i]);
}