LCA

#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define scnaf scanf 
#define itn int
using namespace std;
const int o_o=5e5+5;
const int mod=1e9+7;
const int oo=0x7fffffff;
const int sup=0x80000000;
const int bit=21;
typedef long long ll;
typedef unsigned long long ull;
void read(int &x){
    x=0;int w=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')w=0,ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    x= w?x:-x;
}
int n,m,root;
struct edge{
    int u,v,next;
}g[o_o<<1];
struct E{
 int u,v,next,id;
}Q[o_o<<1];
int head[o_o],cnt=0;
int qhead[o_o],tot=0;
int vis[o_o]={0};
int F[o_o],LCA[o_o]={0};
int fa(int x){return x^F[x]?F[x]=fa(F[x]):x;}
void join(int u,int v){int fx=fa(u),fy=(v);if(fx^fy)F[fx]=fy;}
void add_f(int u,int v){
     g[++cnt]={u,v,head[u]};
     head[u]=cnt;
    }
    void add_s(int u,int v,int id){
     Q[++tot]={u,v,qhead[u],id};
     qhead[u]=tot;
}
void tarjan(int u){
     vis[u]=1;
     for(int i=head[u];~i;i=g[i].next){
      edge v=g[i];
      if(!vis[v.v]){
       tarjan(v.v);
       join(v.v,u);
      }
     }
     for(int i=qhead[u];~i;i=Q[i].next){
      E v=Q[i];
      if(LCA[v.id])continue;
      if(vis[v.v])LCA[v.id]=fa(v.v);
     }
}
int main(){
     cin>>n>>m>>root;
     F[n]=n;me(head,-1);me(qhead,-1);
     for(int i=1;i<n;i++){
      F[i]=i;
      int u,v;
      read(u),read(v);
      add_f(u,v);add_f(v,u);
     }
     for(int i=1;i<=m;i++){
      int u,v;
      read(u),read(v);
      add_s(u,v,i);add_s(v,u,i);
     }
     tarjan(root);
     for(int i=1;i<=m;i++)printf("%d\n",LCA[i]);
}

#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define scnaf scanf 
#define itn int
using namespace std;
const int o_o=5e5+5;
const int mod=1e9+7;
const int oo=0x7fffffff;
const int sup=0x80000000;
const int bit=21;
typedef long long ll;
typedef unsigned long long ull;
void read(int &x){
    x=0;int w=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')w=0,ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    x= w?x:-x;
}
int n,m,root;
struct edge{
     int u,v,next;
}g[o_o<<1];
int head[o_o],cnt=0;
int depth[o_o]={0},f[o_o][bit+1]={0};
void add(int u,int v){
     g[++cnt]={u,v,head[u]};
     head[u]=cnt;
}
void dfs(int u,int fa){
     for(int i=head[u];~i;i=g[i].next){
          edge v=g[i];
          if(v.v^fa){
               depth[v.v]=depth[u]+1;
               f[v.v][0]=u;
               dfs(v.v,u);
          }
     }
}
int LCA(int u,int v){
     if(depth[u]<depth[v])swap(u,v);
     int d=depth[u]-depth[v];
     for(int i=0;(1<<i)<=d;i++)
     if(1<<i&d)u=f[u][i];
     if(u==v)return v;
     for(int i=bit;i>=0;i--)
     if(f[u][i]^f[v][i])u=f[u][i],v=f[v][i];
     return f[u][0];
}
int main(){
     me(head,-1);
     cin>>n>>m>>root;
     for(int i=1;i<n;i++){
          int u,v;
          read(u),read(v);
          add(u,v);add(v,u);
     }
     depth[root]=1;
     dfs(root,-1);
     for(int j=1;j<=bit;j++)
     for(int i=1;i<=n;i++)
     f[i][j]=f[f[i][j-1]][j-1];
     while(m--){
          int u,v;
          read(u),read(v);
          printf("%d\n",LCA(u,v));
     }
}

点
F[l]++,F[r]++,F[lca(l,r)]--,F[grand[lca(l,r)][0]]--;
边
F[l]++,F[r]++,F[lca(l,r)]-=2;