Tarjan LCA 4个hack点全TLE求调

// Luogu P3379
#include <bits/stdc++.h>
using std::cin,std::cout,std::vector;
#define endl "\n"

const int N=5e5+5;
struct Edge{ int to,nxt; }edge[N<<1];
int head[N],cnt=0;
void init(int n) {
    cnt=0;
    for(int i=0;i<=n;++i) head[i]=-1;
    for(int i=0;i<=n<<1;++i) edge[i].nxt=-1;
}
void add_edge(int u,int v) {
    edge[cnt].to=v; edge[cnt].nxt=head[u]; head[u]=cnt++;
}
// Tarjan

struct{ int to,nxt,id; }query[N<<1];
int head_qu[N],cnt_qu=0;
void init_qu(int m) {
    cnt_qu=0;
    for(int i=0;i<=m;++i) head_qu[i]=-1;
    for(int i=0;i<=m<<1;++i) query[i].nxt=-1;
}
void add_query(int x,int y,int id){
    query[cnt_qu].to=y; query[cnt_qu].nxt=head_qu[x];
    query[cnt_qu].id=id; head_qu[x]=cnt_qu++;
}

int S[N];
int find_set(int x) {
    return S[x]==x?x:find_set(S[x]);
}
void init_S(int n) {
    for(int i=0;i<=n;++i) S[i]=i;
}

vector<int>ans;
bool vis[N]={0};
void Tarjan(int now) {
    vis[now]=true;
    for(int i=head[now];~i;i=edge[i].nxt){
        int to=edge[i].to;
        if(vis[to]) continue;
        Tarjan(to);
        S[to]=now;
    }
    for(int i=head_qu[now];~i;i=query[i].nxt){
        int to=query[i].to;
        if(to==now) ans[query[i].id]=now;
        else if(vis[to]) ans[query[i].id]=find_set(to);
    }
}

int main()
{
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,m,s; cin>>n>>m>>s;
    init(n); init_qu(m); init_S(n); ans.resize(m);
    for(int i=1,u,v;i<n;++i){
        cin>>u>>v;
        add_edge(u,v); add_edge(v,u);
    }
    for(int i=0,x,y;i<m;++i){
        cin>>x>>y;
        add_query(x,y,i); add_query(y,x,i);
    }
    Tarjan(s);
    for(auto i:ans) cout<<i<<endl;
    return 0;
}