题解 P3379 【【模板】最近公共祖先（LCA）】

· · 题解

据说没什么Tarjan的题解？

爱离线的Oier看这里！

今天我来给大家介绍一下如何解决LCA问题

显而易见，LCA->LeastCommentAncestors->最近公共祖先问题

那么，容易想到一种暴力做法，即对于任意两点，先让更深的那个节点向上跳，与另个节点处于同一深度；再慢慢一级级爬，直到交与一点为止；很容易想到，当两点均为叶子节点而且LCA为根节点时，效率为O(h)的，这又不是平衡树，深度和n 一个级别是会死的。

有人会说用倍增，可在下不喜欢在线算法，我喜欢稍微快那么一点点的离线Tarjan。比起O((n + m) * logn)的倍增，Tarjan的常数α取决于并查集，在启发式或路径压缩下，是比logn小的。

那么,Tarjan算法过程是什么？

从根节点开始，深搜。 遍历当前访问节点u的所有子节点v，并标记这些子节点v已被访问过。若是v还有子节点，返回2，否则下一步。接着，合并v到u上。（并查集闪亮登场！！！）寻找与当前点u有询问关系的点v。若是v已经被访问过了，则可以确认u和v的最近公共祖先为v被合并到的父亲节点rt。

借用一下一位dalao的图，和思考来做说明

大佬的看法

比如：8−1−14−13 ,此时已经完成了对子树 11 的子树 14 的 dfs 与合并（ 14 子树的集合与 11 所代表的集合合并），如果存在询问 (13,14) ，则其 LCA 即 getf(14) ，即 11 ；如果还存在由节点 13与 已经完成搜索的子树中的 节点的询问，那么处理完。然后合并子树 13 的集合与其父亲 11 当前的集合，回溯到子树 11 ，并深搜完所有 11 的其他未被搜索过的儿子，并完成子树 11 中所有节点的合并，再往上回溯，对节点 11 进行类似的操作即可。

综上，只要不强制在线，Tarjan可优秀了！

（LCA会强制在线？滑稽。只要出题人没病，卡Tarjan干嘛！）

不废话，上代码！！！

//Program written by Liu Zhaozhou ~~~
#include <bits/stdc++.h>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
#include <deque>

#define lowbit(x) x & -x

#pragma GCC optimize(3)

using namespace std;

inline char gc(void)
{
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

template <class T> inline void read(register T &x)
{
    static T flag = 1; x = 0;
    register char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') flag = -1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    x *= flag; return;
}

template <class T> inline void write(register T x)
{
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

template <class T> inline void writeln(register T x)
{
    write(x);
    puts("");
}

template <class T> inline void writeln(T x, char c)
{
    write(x); putchar(c);
}

template <class T> inline void writeln(char c, T x)
{
    putchar(c); write(x);
}

template <class T> inline void chkmax(T &x, const T y) {x > y ? x = x : x = y;}
template <class T> inline void chkmin(T &x, const T y) {x < y ? x = x : x = y;}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

enum {
    maxpool = 500010
};

struct Edge {
    int to, nxt;
} line[maxpool << 1];

struct Info {
    int to, id;
}; vector <Info> vec[maxpool];

int head[maxpool], cnt = 0, rt;

inline void add(int u, int v) {
    line[++cnt] = (Edge) {v, head[u]};
    head[u] = cnt; return;
}

inline void ins(int x, int y, int i) {
    vec[x].push_back((Info) {y, i});
    vec[y].push_back((Info) {x, i});
}

int n, m, ans[maxpool], vis[maxpool], f[maxpool];

inline int getf(int x) {
    return f[x] == x ? f[x] : f[x] = getf(f[x]);
}

inline void tarjan(int dep) {
    vis[dep] = 1;
    for (int e = head[dep]; e; e = line[e].nxt) {
        register int u = line[e].to;
        if (vis[u]) continue;
        tarjan(u); f[u] = dep;
    }

    for (register int i = 0; i < vec[dep].size(); i++)
    {
        int u = vec[dep][i].to, id = vec[dep][i].id;
        if (vis[u] == 2) ans[id] = getf(u);
    }

    vis[dep] = 2; return;
}

int main(void)
{
    read(n); read(m); read(rt);
    for (register int i = 1; i < n; i++) {
        register int u, v;
        read(u); read(v);
        add(u, v); add(v, u);
    } 

    for (register int i = 1; i <= n; i++)
        f[i] = i;

    for (register int i = 1; i <= m; i++) {
        register int u, v;
        read(u); read(v);
        ins(u, v, i);
    }

    tarjan(rt);

    for (register int i = 1; i <= n; i++)
        writeln(ans[i]);

    return 0;
}

/*Tarjan Algorithm solves LCA problems*/