- // 参考博客 https://www.cnblogs.com/jsawz/p/6723221.html
- #include<bits/stdc++.h>
- using namespace std;
- #define maxn 420000
- struct Query{int to,nxt,lca;}q[maxn];
- struct Edge{int to,nxt;}edge[maxn<<1];
- int n,m,p,x,y,tot_e,tot_q,head_q[maxn],head_e[maxn];
- int fa[maxn],vis[maxn];
- void init(){
- memset(head_e,-1,sizeof head_e);
- memset(head_q,-1,sizeof head_q);
- memset(fa,-1,sizeof fa);
- tot_q=tot_q=0;
- }
- void addedge(int u,int v){
- edge[tot_e].to=v;edge[tot_e].nxt=head_e[u];head_e[u]=tot_e++;
- }
- void addquery(int u,int v){
- q[tot_q].to=v;q[tot_q].nxt=head_q[u];head_q[u]=tot_q++;
- }
- int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
- int dfs(int u){
- fa[u]=u;vis[u]=1;
- for(int i=head_e[u];i!=-1;i=edge[i].nxt){
- int v=edge[i].to;
- if(vis[v])continue;
- dfs(v);fa[v]=u;
- }
- for(int i=head_q[u];i!=-1;i=q[i].nxt){
- int v=q[i].to;
- if(vis[v]) q[i].lca=q[i^1].lca=find(v);
- }
- }
- int main(){
- init();
- cin>>n>>m>>p;
- for(int i=1;i<n;i++){
- cin>>x>>y;
- addedge(x,y);
- addedge(y,x);
- }
- for(int i=0;i<m;i++){
- cin>>x>>y;
- addquery(x,y);
- addquery(y,x);
- }
- dfs(p);
- for(int i=0;i<m;i++)
- printf("%d",q[i<<1].lca);
- }
来源: http://www.bubuko.com/infodetail-2947792.html