点的距离

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1277 字

给定n个点的树和Q个询问，求每次询问两点x、

一本通
例

正文

/*
原题：T1552 「一本通 4.4 例 1」点的距离
题意：给定 n 个点的树和 Q 个询问，求每次询问两点 x、y 之间的距离。
思路：倍增预处理每个点的 2^k 级祖先与深度；两点距离 = depth[x]+depth[y]-2*depth[lca(x,y)]，树边长度视为 1。
复杂度：预处理 O(n log n)，每次询问 O(log n)。
易错点：lca 提升时先对齐深度再同步上跳；根节点深度设为 0。
*/
#include <bits/stdc++.h>
using namespace std;
const int LOG=20;
int n,Q;
vector<vector<int>> g;
vector<int> dep;
vector<vector<int>> up;
void dfs(int u,int p){
    up[u][0]=p;
    for(int i=1;i<LOG;i++) up[u][i]=up[up[u][i-1]][i-1];
    for(int v:g[u]){
        if(v==p) continue;
        dep[v]=dep[u]+1;
        dfs(v,u);
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=LOG-1;i>=0;i--)
        if(dep[x]-(1<<i)>=dep[y]) x=up[x][i];
    if(x==y) return x;
    for(int i=LOG-1;i>=0;i--)
        if(up[x][i]!=up[y][i]){ x=up[x][i]; y=up[y][i]; }
    return up[x][0];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    g.assign(n+1,vector<int>());
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dep.assign(n+1,0);
    up.assign(n+1,vector<int>(LOG,0));
    dfs(1,0);
    cin>>Q;
    while(Q--){
        int x,y;
        cin>>x>>y;
        int l=lca(x,y);
        cout<<dep[x]+dep[y]-2*dep[l]<<'\n';
    }
    return 0;
}

点的距离

正文

一本通·提高篇的其它内容