题解：P9245 [蓝桥杯 2023 省 B] 景区导游

· · 题解

正在找关于 LCA 的题，然后就发现了这题。本来以为是板子题，没想到被输出卡了。本蒟蒻就在此写篇题解来晶石后人

P9245 题解

首先，看到路线构成了一棵树，并且要求两点之间的距离，明显的 LCA 的题。再看一下数据范围：100000，符合 LCA 的时间复杂度，就可以用倍增来求。再看下细节。

由于每条路带有权值，想到可以在求 LCA 是用前缀和来维护。用链式前向星存图，定义 dis[i] 代表点 i 距离根节点的边权之和。维护如下：


inline void dfs(int x, int fa){
    f[x][0] = fa;
    dep[x] = dep[fa] + 1;
    for (int i = 1; i <= 19; i++)
        f[x][i] = f[f[x][i - 1]][i - 1];
    for (int i = head[x]; i; i = e[i].nxt){
        int v = e[i].v;
        int w = e[i].w;
        if (v == fa) continue;
        dis[v] = dis[x] + w;
        dfs(v, x);
    }
}

最后查询是返回点 a 和点 b 之间的最短路径：

inline int query(int a, int b){
    return dis[a] + dis[b] - 2 * dis[lca(a, b)];
}

注意：

题目要求输出的是跳过点 i 后乘车的时间，所以可以提前求出乘车的总时间，在便利到点 i 时减去从 i - 1 到 i 和从 i 到 i + 1 的时间，然后加上从 i - 1 到 i + 1 的时间。别忘了特判当 i 等于 1 和 k 的情况。

代码如下：

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 1e5 + 10;

int n, k;
int dep[N], f[N][20], ans[N], a[N], dis[N];
struct edge{
    int u, v, nxt, w;
}e[2 * N];
int cnt;
int head[N];

inline void add(int u, int v, int w){
    cnt++;
    e[cnt].u = u;
    e[cnt].v = v;
    e[cnt].w = w;
    e[cnt].nxt = head[u];
    head[u] = cnt;
}

inline void dfs(int x, int fa){
    f[x][0] = fa;
    dep[x] = dep[fa] + 1;
    for (int i = 1; i <= 19; i++)
        f[x][i] = f[f[x][i - 1]][i - 1];
    for (int i = head[x]; i; i = e[i].nxt){
        int v = e[i].v;
        int w = e[i].w;
        if (v == fa) continue;
        dis[v] = dis[x] + w;
        dfs(v, x);
    }
}

inline int lca(int x, int y){
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 19; i >= 0; i--)
        if (dep[f[x][i]] >= dep[y]) x = f[x][i];
    if (x == y) return x;
    for (int i = 19; i >= 0; i--){
        if (f[x][i] != f[y][i]){
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];
}

inline int query(int a, int b){
    return dis[a] + dis[b] - 2 * dis[lca(a, b)];
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i < n; i++){
        int u, v, t;
        cin >> u >> v >> t;
        add(u, v, t);
        add(v, u, t);
    }
    dep[1] = 1;
    dfs(1, 0);
    int las = 1;
    for (int i = 1; i <= k; i++)
        cin >> a[i];
    int sum = 0;
    for (int i = 2; i <= k; i++)
        sum += query(a[i - 1], a[i]);
    for (int i = 1; i <= k; i++){
        if (i == 1)
            ans[i] = sum - query(a[1], a[2]);
        else if (i == k)
            ans[i] = sum - query(a[k - 1], a[k]);
        else 
            ans[i] = sum - query(a[i - 1], a[i]) - query(a[i], a[i + 1]) + query(a[i - 1], a[i + 1]);
    }
    for (int i = 1; i <= k; i++)
        cout << ans[i] << " ";
    return 0;
}