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]);
}