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

· · 题解

最近正在学 LCA，正好看到蓝桥杯省赛这题，似乎刚放上去还没有题解，正好作为本蒟蒻第一篇题解练练手结果发现不会写题解。

题意分析

题意比较简单，在一棵有 N 个点的无向有权树上选出 K 个点，随后有 K 个询问，每次询问会跳过一个点，跳过的点从1、2、3依次到 K，求每次依次访问剩余点的路径权值和最小值。

解题思路

首先很容易得出：由于访问顺序固定，任意连续访问点之间的路径权值和都要最小，这样按顺序访问所有点后的路径权值和一定最小。而一棵无向树上任意两点的最短路径有且只有一条，并且经过这两点的 LCA 即最近公共祖先（不管边带不带权都一样）。这样的最短路径很好求得，用树上前缀和 sum[i] 表示树根到结点i的路径权值和，那么任意两点 a 和 b 的最短路径为

dis(a,b)=sum[a]+sum[b]-2 \times \operatorname{LCA}(a,b)

再求出按原访问顺序的路径权值前缀和，对于 A _ {i} 有

ans[i]=dis(A _ {1},A _ {2})+dis(A _ {2},A _ {3})+\dots+dis(A _ {i-1},A _ {i})(2 \le i \le K)

那么当跳过 A _ {i} 时，答案就是

\begin{cases} ans[K]-ans[2] & i = 1 \\ ans[i-1]+dis(a[i-1],a[i+1])+ans[K]-ans[i+1] & 2 \le i \le K-1 \\ ans[K-1] & i = K \end{cases}

那么问题来到如何求出一些给定点对的 LCA。这里本蒟蒻用了离线算法 Tarjan 算法，因为懒得写倍增因为赛时可以比较快捷地实现。

简单来说，此题需要以下步骤：读入树后，进行一次 DFS 预处理出所有结点的树上前缀和 sum[i]。读入游览线路，记录下相邻数对和间隔数对。跑一遍 Tarjan 算法，求出按照原访问顺序的路径权值前缀和，求出答案。时间复杂度为 O\left(m\,\alpha(m+n, n) + n\right)。

具体代码

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

long long a[100005];

bool vis1[100005];
long long sum[100005];

bool vis2[100005];
long long fa[100005];
vector<long long>q[100005];//保存要查询的点对，离线查询

map<pair<long long, long long>, long long>ma;//保存点对及其LCA

long long ans[100005];

struct node {
    long long v;
    long long t;
} edge;

vector<struct node>g[100005];

long long find(long long x) {
    if (fa[x] == x) {
        return x;
    } else {
        return fa[x] = find(fa[x]);
    }
}

void dfs(long long x) {//预处理求出树上前缀和
    vis1[x] = true;

    for (long long i = 0; i < g[x].size(); i++) {
        if (vis1[g[x][i].v] != true) {
            sum[g[x][i].v] = g[x][i].t + sum[x];
            dfs(g[x][i].v);
        }
    }
    return;
}

void tarjan(long long x) {//标准tarjan模板
    vis2[x] = true;

    for (long long i = 0; i < g[x].size(); i++) {
        if (vis2[g[x][i].v] == false) {
            tarjan(g[x][i].v);
            fa[g[x][i].v] = x;
        }
    }

    for (long long i = 0; i < q[x].size(); i++) {
        if (vis2[q[x][i]] == true) {
            ma[ {x, q[x][i]}] = find(q[x][i]);
            ma[ {q[x][i], x}] = find(q[x][i]);
        }
    }
    return;
}

long long get_dis(long long x, long long y) {//求出树上两点最短路径
    return sum[x] + sum[y] - 2 * sum[ma[ {x, y}]];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    long long n, k;
    cin >> n >> k;

    for (long long i = 1; i < n; i++) {
        long long u, v, t;
        cin >> u >> v >> t;

        g[u].push_back({v, t});
        g[v].push_back({u, t});
    }

    dfs(1);//预处理出树上前缀和

    for (long long i = 1; i <= k; i++) {//离线保存所需查询
        cin >> a[i];
        if (i >= 2) {//相邻点对
            q[a[i]].push_back(a[i - 1]);
            q[a[i - 1]].push_back(a[i]);
        }
        if (i >= 3) {//间隔点对
            q[a[i]].push_back(a[i - 2]);
            q[a[i - 2]].push_back(a[i]);
        }
    }

    for (long long i = 1; i <= n; i++) {//tarjan算法初始化
        fa[i] = i;
    }

    tarjan(1);//预处理出所求LCA

    for (long long i = 2; i <= k; i++) {//按原访问顺序的路径权值前缀和
        ans[i] = ans[i - 1] + get_dis(a[i], a[i - 1]);
    }

    for (long long i = 1; i <= k; i++) {//分段得出答案
        if (i == 1) {
            cout << ans[k] - ans[2] << " ";
        } else if (i == k) {
            cout << ans[k - 1] << " ";
        } else {
            cout << ans[i - 1] + get_dis(a[i - 1], a[i + 1]) + ans[k] - ans[i + 1] << " ";
        }
    }
    return 0;
}

提交，AC，然后这篇题解就结束了果然写题解好难。