提交记录

#include<bits/stdc++.h>
using namespace std;
struct Node{
    vector<int>child;
    int size,father,deep;
    int bestSon,top;
};
map<int,set<int>>graph;
map<int,Node>tree;
int n,m,s;
int build(int x,int father,int deep){
    tree[x].father = father;
    tree[x].deep = deep;
    int k=-1,v=-1,t;
    for(auto i:graph[x]){
        if(i == father)continue;
        t = build(i,x,deep+1);
        if(t>v){
            v = t;
            k = i;
        }
        tree[x].child.push_back(i);
    }
    tree[x].bestSon = k;
    tree[x].size = graph[x].size();
    return tree[x].size;
}
void link(int x,int top){
    tree[x].top = top;
    if(tree[x].bestSon==-1)return;
    for(auto i:tree[x].child){
        if(tree[x].bestSon==i)link(i,top);
        else link(i,i);
    }
}
int lca(int x,int y){
    while(tree[x].top != tree[y].top){
        if(tree[x].deep>tree[y].deep){
            if(tree[x].top == x)x = tree[x].father;
            else x = tree[x].top;
        }
        else{
            if(tree[y].top == y)y = tree[y].father;
            else y = tree[y].top;
        }

    }
    return tree[x].deep > tree[y].deep ? y : x;
}
int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        graph[x].insert(y);
        graph[y].insert(x);
    }
    build(s,s,1);
    link(s,s);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n", lca(x,y));
    }
}