题解 | 【模板】最近公共祖先（LCA）

import sys
input=sys.stdin.readline
def solve():
    n,m,r=map(int,input().split())
    adj=[[] for _ in range(n+1)]
    #邻接表存图
    for _ in range(n-1):
        u,v=map(int,input().split())
        adj[u].append(v)
        adj[v].append(u)
    #dfs从r遍历,并存储父节点
    parents=[0]*(n+1)
    layors=[0]*(n+1)
    stack=[(r,0,1)]#当前节点,当前节点父节点,当前层
    while stack:
        u,p,lay=stack.pop()
        parents[u]=p
        layors[u]=lay
        for v in adj[u]:
            if v==p:continue
            stack.append((v,u,lay+1))
            #print((v,u))
    #生成st表
    st=[[0]*20 for _ in range(n+1)]
    for i in range(n+1):
        st[i][0]=parents[i]
    for j in range(1,20):
        for i in range(n+1):
            st[i][j]=st[st[i][j-1]][j-1]
    #print(st)
    #print(layors)
    for _ in range(m):
        a,b=map(int,input().split())
        #倍增跑到同层
        if layors[a]>layors[b]:a,b=b,a
        #print("===>",_,a,b,layors[a],layors[b])
        h=layors[b]-layors[a]
        i=0
        #二进制分解以跑到同一层
        while h:
            if h&1:b=st[b][i]
            i+=1
            h>>=1
        #print("===>",_,a,b,layors[a],layors[b])
        if a==b:#一样表示找到
            outs.append(a)
            continue
        #不一样则找lca下面的一个
        for i in range(19,-1,-1):
            if st[a][i]!=st[b][i]:
                a=st[a][i]
                b=st[b][i]  
        #print("==>",a,b,st[a][0])  
        outs.append(st[a][0])


outs=[]
solve()
print("\n".join(map(str,outs)))

倍增求lca，步骤见注释