蓝桥杯2023年-景区导游（倍增法求LCA）

题目描述

某景区一共有 N 个景点，编号 1 到 N。景点之间共有 N − 1 条双向的摆渡车线路相连，形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行，需要花费一定的时间。

小明是这个景区的资深导游，他每天都要按固定顺序带客人游览其中 K 个景点：A1, A2, . . . , AK。今天由于时间原因，小明决定跳过其中一个景点，只带游客按顺序游览其中 K − 1 个景点。具体来说，如果小明选择跳过 Ai，那么他会按顺序带游客游览 A1, A2, . . . , Ai−1, Ai+1, . . . , AK, (1 ≤ i ≤ K)。

请你对任意一个 Ai，计算如果跳过这个景点，小明需要花费多少时间在景点之间的摆渡车上？

思路

难点在于如何快速求两点之间的距离。

在树状结构中，两点距离==两点到达共同祖先LCA的距离之和。我们可以先预处理出各结点到根节点的距离。然后借助LCA算法求两点的LCA，则两点之间的距离==两点到根节点的距离之和-LCA到根节点的距离*2；

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
#define int long long
vector<pair<int,int>>son[N];
int dep[N];
int dist[N];
int f[N][30];
void dfs(int u,int p,int d){
    dep[u]=dep[p]+1;f[u][0]=p;dist[u]=d;
    for(int i=1;(1<<i)<=dep[u];i++){
        f[u][i]=f[f[u][i-1]][i-1];
    }
    for(auto it:son[u]){
        if(it.first!=p){
            dfs(it.first,u,d+it.second);
        }
    }
}
int lca(int a,int b){
    if(dep[a]<dep[b])swap(a,b);
    for(int i=20;i>=0;i--){
        if(dep[f[a][i]]>=dep[b])a=f[a][i];
        if(a==b)return a; 
    }
    for(int i=20;i>=0;i--){
        if(f[a][i]!=f[b][i])a=f[a][i],b=f[b][i];
    }
    return f[a][0];
}
int get(int a,int b){
    return dist[a]+dist[b]-2*dist[lca(a,b)];
}
signed main(){
    int n,k;cin>>n>>k;
    for(int i=0;i<n-1;i++){
        int a,b,d;cin>>a>>b>>d;
        son[a].push_back({b,d});
        son[b].push_back({a,d});
    }
    dfs(1,0,0);
    int sum=0;
    vector<int>nod(k);
    for(int i=0;i<k;i++){
        cin>>nod[i];
    }
    for(int i=1;i<k;i++){
        sum+=get(nod[i],nod[i-1]);
    }
    for(int i=0;i<k;i++){
        int ans=sum;
        if(i!=0)ans-=get(nod[i-1],nod[i]);
        if(i!=k-1)ans-=get(nod[i],nod[i+1]);
        if(i!=0&&i!=k-1)ans+=get(nod[i-1],nod[i+1]);
        cout<<ans<<' ';
    }
}