tarjan不是O(m+n)的吗??????????
#include <bits/stdc++.h>
using namespace std;
vector<int> a[500005], query[500005], query_id[500005];
int n, m, s, lca[500005], v[500005], fa[500005];
int get(int x) {
if (x == fa[x]) return x;
return fa[x] = get(fa[x]);
}
void tarjan(int x) {
v[x] = 1;
for (int i = 0; i < a[x].size(); i ++ ) {
int y = a[x][i];
if (v[y]) continue;
tarjan(y);
fa[y] = x;
}
for (int i = 0; i < query[x].size(); i ++ ) {
int y = query[x][i], id = query_id[x][i];
if (v[y] == 2)
lca[id] = get(y);
}
v[x] = 2;
}
int main() {
scanf("%d%d%d", &n, &m, &s);
for (int i = 1; i <= n; i ++ ) fa[i] = i;
for (int i = 1, x, y; i < n; i ++ ) {
scanf("%d%d", &x, &y);
a[x].push_back(y);
a[y].push_back(x);
}
for (int i = 1, x, y; i <= m; i ++ ) {
scanf("%d%d", &x, &y);
query[x].push_back(y), query_id[x].push_back(i);
query[y].push_back(x), query_id[y].push_back(i);
}
tarjan(s);
for (int i = 1; i <= m; i ++ )
printf("%d\n", lca[i]);
}