[success]原题:https://www.luogu.org/problem/show?pid=3379[/success]
题意，给你一棵树，求几对点的LCA...

我的做法:
由于Tarjan够简单的，所以我就用了Tarjan...
这个算法真的很简单！！但是超级好理解的！！
以前从来没写过LCA...这也是第一次吧

O(α(n) + M)

代码:
[code lang="cpp"]
#include<cstdio>
#include<iostream>
#include<cstring>
#define MAXN 600050
#define MAXM 600050
using namespace std;
int headt[MAXN], headq[MAXN];
int ans[MAXM];
int f[MAXN], vis[MAXN];
int n, m, s;
int tec = 0, qec = 0;

struct edge{
int to, next;
}te[MAXN * 2];

struct edg2{
int to, next, idx;
}qe[MAXN * 2];

int fin(int v){
// cout << v << endl;
if (f[v] != v) f[v] = fin(f[v]);
return f[v];
}

void tarjan(int u){
// cout << u << endl;
f[u] = u;
vis[u] = 1;
for (int i = headt[u]; i != -1; i = te[i].next){
// cout << i << endl;
int v = te[i]. to;
if (!vis[v]){
tarjan(v);
f[v] = u;
}
}
for (int i = headq[u]; i != -1; i = qe[i].next){
// cout << i << endl;
int v = qe[i].to;
int idx = qe[i].idx;
if (vis[v]) ans[idx] = fin(v);
}
}

void addt(int u, int v){
te[tec].to = v;
te[tec].next = headt[u];
headt[u] = tec++;
}

void addq(int u, int v, int idx){
qe[qec].to = v;
qe[qec].idx = idx;
qe[qec].next = headq[u];
headq[u] = qec++;
}

int main(){
int x, y;
memset(vis, 0, sizeof(vis));
scanf("%d%d%d", &n, &m, &s);
for (int i = 0; i <= n; i++) headt[i] = -1, headq[i] = -1;
for (int i = 0; i < n - 1; i++){
scanf("%d%d", &x, &y);
addt(x, y);
addt(y, x);
}
for (int i = 0; i < m; i++){
scanf("%d%d", &x, &y);
addq(x, y, i);
addq(y, x, i);
}
tarjan(s);
for (int i = 0; i < m; i++){
printf("%d\n", ans[i]);
}
}
[/code]