第十四届蓝桥杯省赛C++B组I题【景区导游】题解（AC）

解题思路

题目已给出地图为一个 $n$ 个点，$n-1$ 条路线的树。

对于计算树中任意两点的距离，我们可以使用 LCA 算法进行快速计算。

假设 $a,b$ 的最近公共祖先为 $c$，那么 $a,b$ 之间的距离为 $dist[a]+dist[b]-2\times dist[c]$，其中 $dist[x]$ 表示从根节点到 $x$ 点的距离。

所以我们可以先算出原定路线所消耗的时间 $res$，再进行删点删边操作：

1. 假设删掉的为第 $1$ 个点，相当于删掉从 $1$ 号点到 $2$ 号点的边，相当于从 $2$ 号点开始。那么答案应该等于
   $$res-get\_dist(q[1],q[2])$$
2. 假设删掉的为第 $i(1<i<m)$ 个点，相当于删掉从 $i-1$ 号点到 $i$ 号点的边和从 $i$ 号点到 $i+1$ 号点的边，并且补上一条从 $i-1$ 号点到 $i+1$ 号点的边，那么答案应该等于
   $$res-get\_dist(q[i-1],q[i])-get\_dist(q[i],q[i+1])+get\_dist(q[i-1],q[i+1])$$
3. 假设删掉的为第 $m$ 个点，相当于删掉从 $m-1$ 号点到 $m$ 号点的边，相当于从 $m-1$ 号点结束。那么答案应该等于
   $$res-get\_dist(q[m-1],q[m])$$

AC_Code

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10, M = N * 2;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int depth[N];
LL dist[N];
int fa[N][20];
int q[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

void bfs()
{
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[1] = 1;
    queue<int> q;
    q.push(1);

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        for (int i = h[t]; ~i; i = ne[i] )
        {
            int j = e[i];
            if (depth[j] <= depth[t] + 1)
                continue;
            depth[j] = depth[t] + 1;
            dist[j] = dist[t] + w[i];
            fa[j][0] = t;
            for (int k = 1; k <= 19; ++ k )
                fa[j][k] = fa[fa[j][k - 1]][k - 1];
            q.push(j);
        }
    }
}

int get_lca(int a, int b)
{
    if (depth[a] < depth[b])
        swap(a, b);
    for (int i = 19; i >= 0; -- i )
        if (depth[fa[a][i]] >= depth[b])
            a = fa[a][i];
    if (a == b)
        return a;

    for (int i = 19; i >= 0; -- i )
        if (fa[a][i] != fa[b][i])
        {
            a = fa[a][i];
            b = fa[b][i];
        }

    return fa[a][0];
}

LL get_dist(int a, int b)
{
    int c = get_lca(a, b);
    return dist[a] + dist[b] - dist[c] * 2;
}

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

    cin >> n >> m;

    memset(h, -1, sizeof h);

    for (int i = 0; i < n - 1; ++ i )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }

    for (int i = 1; i <= m; ++ i )
        cin >> q[i];

    bfs();

    LL res = 0;
    for (int i = 1; i <= m - 1; ++ i )
        res += get_dist(q[i], q[i + 1]);

    for (int i = 1; i <= m; ++ i )
    {
        if (i == 1)
            cout << res - get_dist(q[1], q[2]) << ' ';
        else if (i < m)
            cout << res - get_dist(q[i - 1], q[i]) - get_dist(q[i], q[i + 1]) + get_dist(q[i - 1], q[i + 1]) << ' ';
        else
            cout << res - get_dist(q[m - 1], q[m]) << ' ';
    }

    cout << endl;

    return 0;
}

【在线测评】