题解

LCA（最近公共祖先）模板，对数复杂度查询

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
typedef long long ll;
const ll N = 5e5 + 5;
ll n, m, s;
vector<vector<ll>> edge;
ll dep[N];
ll f[N][20];
void readedge(){
    edge.resize(n+1);
    for(int i=1; i<n; i++){
        ll x, y;
        cin >> x >> y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
}
void maketree(){
    f[s][0] = s;
    queue<ll> q;
    q.push(s);
    dep[s] = 1;
    while(q.size()){
        ll r = q.front();
        q.pop();
        for(ll j:edge[r]){
            if(!f[j][0]){
                f[j][0] = r;
                dep[j] = dep[r] + 1;
                q.push(j);
            }
        }
    }
}
void st(){
    for(int j=1; j<20; j++){
        for(int i=1; i<=n; i++){
            f[i][j] = f[f[i][j-1]][j-1];
        }
    }
}
ll LCA(ll x, ll y){
    if(x == y) return x;
    if(dep[y] > dep[x]) swap(x, y);
    ll t = dep[x] - dep[y];
    ll cnt = 0;
    while(t){
        if(t % 2 == 1) x = f[x][cnt];
        cnt++;
        t /= 2;
    }
    if(x == y) return x;
    ll maxstep = 19;
    for(int i=maxstep; i>=0; i--){
        if(f[x][i] != f[y][i]){
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];
}
void solve(){
    ll x, y;
    cin >> x >> y;
    cout << LCA(x, y) << endl;
}
int main(){
    cin >> n >> m >> s;
    readedge();
    maketree();
    st();
    while(m--){
        solve();
    }
    return 0;
}