contest_tarjan_LCA_源码

#include<bits/stdc++.h> using namespace std; struct node{ int to,nxt,lca,w; }; const int MAXN = 500010; node edge[MAXN*2],qedge[MAXN*2]; int head[MAXN*2],qhead[MAXN*2]; int father[MAXN],vis[MAXN],dis[MAXN]; int l1,l2; void add(int u,int v,int w) { edge[++l1].to=v; edge[l1].w=w; edge[l1].nxt=head[u]; head[u]=l1; } void qadd(int u,int v) { qedge[++l2].to=v; qedge[l2].nxt=qhead[u]; qhead[u]=l2; } int find(int x) { if(father[x]!=x) father[x]=find(father[x]); return father[x]; } void bfs(int s)//bfs求深度 { queue<int> q; memset(dis,-1,sizeof(dis)); q.push(s);dis[s]=0; while(!q.empty()) { int now=q.front(); q.pop(); for(int i=head[now];i;i=edge[i].nxt) { int v=edge[i].to; if(dis[v]==-1) { dis[v]=dis[now]+edge[i].w; q.push(v); } } } } void dfs(int u) { father[u]=u; vis[u]=1; for(int i=head[u];i;i=edge[i].nxt) { int v=edge[i].to; if(!vis[v]) { dfs(v); father[v]=u; } } for(int i=qhead[u];i;i=qedge[i].nxt) { int v=qedge[i].to; if(vis[v]) { qedge[i].lca=find(v); if(i%2) { qedge[i+1].lca=qedge[i].lca; } else { qedge[i-1].lca=qedge[i].lca; } } } } int main() { int n,m,s; scanf("%d%d%d",&n,&m,&s); for(int i=1;i<n;i++) { int u,v; scanf("%d%d",&u,&v); add(u,v,0); add(v,u,0); } for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); qadd(u,v); qadd(v,u); } dfs(s); for(int i=1;i<=m;i++) { printf("%d\n",qedge[i*2].lca); } }