信息学奥赛一本通T1552-点的距离 树链剖分求LCA

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
#define ll long long
#define endl '\n'
const ll N=1e5+5;
ll n,q;
vector<ll> e[N];
ll fa[N],dep[N],son[N],sz[N],top[N];
void dfs1(ll u,ll f){
    fa[u]=f,dep[u]=dep[f]+1,sz[u]=1;
    for(ll v:e[u]){
        if(v==f)continue;
        dfs1(v,u);
        sz[u]+=sz[v];
        if(sz[son[u]]<sz[v])son[u]=v;
    }
}
void dfs2(ll u,ll t){
    top[u]=t;
    if(!son[u])return;
    dfs2(son[u],t);
    for(ll v:e[u]){
        if(v==son[u]||v==fa[u])continue;
        dfs2(v,v);
    }
}
ll lca(ll u,ll v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        u=fa[top[u]];
    }
    return dep[u]<dep[v]?u:v;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);//加速输入输出
    cin>>n;
    for(ll i=1;i<n;i++){
        ll x,y;cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs1(1,0);
    dfs2(1,1);
    cin>>q;
    while(q--){
        ll x,y;cin>>x>>y;
        ll k=lca(x,y);
        cout<<dep[x]+dep[y]-2*dep[k]<<endl;//公式，应该不用解释吧
    }
    return 0;
}