Dis

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

给出n个点的带权树，多次询问两点之间的最短距

一本通
练习

正文

/*
原题：T1556 「一本通 4.4 练习 1」Dis
题意：给出 n 个点的带权树，多次询问两点之间的最短距离（边为双向、有权）。
思路：倍增求 LCA；用 dis[u] 记录根到 u 的带权距离，询问答案 = dis[x]+dis[y]-2*dis[lca(x,y)]。
复杂度：预处理 O(n log n)，每次询问 O(log n)。
易错点：距离用带权 dis，不是深度；边权可能很大要用 long long。
*/
#include <bits/stdc++.h>
using namespace std;
const int LOG=20;
int n,m;
vector<vector<pair<int,int>>> g;
vector<int> dep;
vector<long long> dis;
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(auto&e:g[u]){
        int v=e.first,w=e.second;
        if(v==p) continue;
        dep[v]=dep[u]+1;
        dis[v]=dis[u]+w;
        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>>m;
    g.assign(n+1,vector<pair<int,int>>());
    for(int i=1;i<n;i++){
        int x,y,k;
        cin>>x>>y>>k;
        g[x].push_back({y,k});
        g[y].push_back({x,k});
    }
    dep.assign(n+1,0);
    dis.assign(n+1,0);
    up.assign(n+1,vector<int>(LOG,0));
    dfs(1,0);
    while(m--){
        int x,y;
        cin>>x>>y;
        int l=lca(x,y);
        cout<<dis[x]+dis[y]-2*dis[l]<<'\n';
    }
    return 0;
}

Dis

正文

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