蓝桥杯真题 - 景区导游 - 题解

题目链接：https://www.lanqiao.cn/problems/3516/learning/

个人评价：难度 4 星（满星：5）
前置知识：LCA

整体思路

• 假设能快速算出任意两个节点 $u,v$ 之间的距离，就可以先算一遍所有 $A_i$ 与 $A_{i+1}$ 之间的距离总和，记为 $disSum={\sum }_{i=1}^{i=K-1}di{s}_{A_i,A_{i+1}}$，然后考虑跳过每一个 $A_i(2\le i\le K-1)$ 节点的情况：把 $disSum$ 减去 $(di{s}_{A_{i-1},A_i}+di{s}_{A_i,A_{i+1}})$，再加上 $di{s}_{A_{i-1},A_{i+1}}$ 就是跳过节点 $A_i$ 的结果（当 $i=1$ 与 $i=K$ 时直接把 $disSum$ 分别减去 $di{s}_{A_1,A_2}$ 和 $di{s}_{A_{K-1},A_K}$ 即可）；
• 先用一个 dfs 跑出所有节点 $u$ 到根节点的距离 $di{s}_{u,root}$，然后任意两个节点之间的距离，就是它们到根节点之间的距离总和减去两倍的它们最近公共祖先到根节点的距离，假设用 LCA 求出最近公共祖先节点为 $f$，则任意两点间距离为

$$di{s}_{u,v}=di{s}_{u,root}+di{s}_{v,root}-2\times di{s}_{f,root}$$

过题代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int Log = 20;
const int maxn = 100000 + 100;
struct Node {
    int pos;
    LL dis;
    Node() {}
    Node(int pos, LL dis) : pos(pos), dis(dis) {}
};

int n, k, u, v, t, idCnt;
int st[maxn][Log];
LL disSum;
vector<Node> G[maxn];
int id[maxn], a[maxn];
LL dis[maxn], disPre[maxn];

void dfs(int root, int fa) {
    id[root] = ++idCnt;
    st[root][0] = fa;
    for(int j = 1; j < Log; ++j) {
        st[root][j] = st[st[root][j - 1]][j - 1];
    }
    for (Node &node: G[root]) {
        int pos = node.pos;
        if (pos != fa) {
            dis[pos] = dis[root] + node.dis;
            dfs(pos, root);
        }
    }
}

int lca(int x, int y) {
    if(x == y) {
        return x;
    }
    if(id[x] > id[y]) {
        swap(x, y);
    }
    for(int i = Log - 1; i >= 0; --i) {
        if(id[st[y][i]] > id[x]) {
            y = st[y][i];
        }
    }
    return st[y][0];
}

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif // ExRoc
    ios::sync_with_stdio(false);

    cin >> n >> k;
    for (int i = 1; i < n; ++i) {
        cin >> u >> v >> t;
        G[u].push_back(Node(v, t));
        G[v].push_back(Node(u, t));
    }
    dfs(1, 1);
    for (int i = 1; i <= k; ++i) {
        cin >> a[i];
    }
    for (int i = 2; i <= k; ++i) {
        int f = lca(a[i], a[i - 1]);
        disPre[i] = dis[a[i]] + dis[a[i - 1]] - 2 * dis[f];
        disSum += disPre[i];
    }
    cout << disSum - disPre[2] << " ";
    for (int i = 1; i + 2 <= k; ++i) {
        int f = lca(a[i], a[i + 2]);
        cout << disSum - disPre[i + 1] - disPre[i + 2] + dis[a[i]] + dis[a[i + 2]] - 2 * dis[f] << " ";
    }
    cout << disSum - disPre[k] << endl;

    return 0;
}