trudbot

用户名：2185759039

访问量：936

签　名：

等　　级
排　　名	22952
经　　验	485
参赛次数	0
文章发表	4
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

倍增LCA算法
浏览：267

极简线性DP
浏览：267

树上差分
浏览：130

你可能喜欢

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

优质题解

倍增LCA算法

　　作者: trudbot　　　　发表时间：2023-04-10 21:22:47 浏览：267　|　评论：0　

原题链接：蓝桥杯2023年第十四届省赛真题-景区导游

[完整题解](https://blog.csdn.net/qq_60775983/article/details/130043884)
## 试题I: 景区导游

### 题意描述

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

小明是这个景区的资深导游，他每天都要按固定顺序带客人游览其中K 个景点：A1; A2; : : : ; AK。今天由于时间原因，小明决定跳过其中一个景点，只带游客按顺序游览其中K − 1 个景点。具体来说，如果小明选择跳过Ai，那么他会按顺序带游客游览$A_1，A_2... A_{i−1},A_{i+1},A_K$ (1 ≤ i ≤ K)。请你对任意一个Ai，计算如果跳过这个景点，小明需要花费多少时间在景点之间的摆渡车上？

### 带权LCA

要确定的一点是， 由于题中的图是一棵树， 所以对于任意两个顶点， 它们的最短路径就是它们的简单路径。

求树中两个结点的简单路径距离， 可以想到利用它们的最近公共祖先即LCA。

设$dist[u]$为u顶点到根结点的距离， 那么u和v的距离即为$dist[u] + dist[v] - 2 * dist[lca(u, v)]$.

因此本题就是一道LCA的模板题， 使用倍增法或者tarjan算法都是可以的, 具体的算法知识请自行去学习。

距离可能会爆int， 因此建议是所有整型都用long long， 避免麻烦。

### 参考代码
以下是使用倍增LCA算法的参考代码， 时间复杂度O(klogn)
```cpp
//
// Created by trudbot on 2023/4/10.
//
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
using ll = long long;
vector<pair<int, int>> g[N];
ll dep[N], f[N][30], dist[N];

//倍增LCA预处理
void dfs(int u, int fa, ll d) {
    dep[u] = dep[fa] + 1, dist[u] = d, f[u][0] = fa;
    for (int i = 1; (1 << i) <= dep[u]; i ++) f[u][i] = f[f[u][i - 1]][i - 1];
    for (auto &p : g[u]) {
        if (p.first == fa) continue;
        dfs(p.first, u, d + p.second);
    }
}

//求a和b的lca
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];
}

ll get(int a, int b) {
    return dist[a] + dist[b] - 2 * dist[lca(a, b)];
}

int main () {
    int n, k; cin >> n >> k;
    for (int i = 1; i < n; i ++) {
        int u, v, t; cin >> u >> v >> t;
        g[u].push_back({v, t}), g[v].push_back({u, t});
    }
    vector<int> a(k);
    for (auto &x : a) cin >> x;
    dfs(1, 0, 0);
	
	//求出原本整条路径的和
    ll sum = 0;
    for (int i = 1; i < k; i ++) sum += get(a[i - 1], a[i]);
	
	//依次求出删除每个点时的和
    for (int i = 0; i < k; i ++) {
        ll ans = sum;
		//减去当前顶点和左右顶点的路径距离
        if (i != 0) ans -= get(a[i], a[i - 1]);
        if (i != k - 1) ans -= get(a[i], a[i + 1]);
		//左右都有顶点时， 要把两个顶点接到一起
        if (i != 0 && i != k - 1) ans += get(a[i - 1], a[i + 1]);
        cout << ans << " ";
    }
    return 0;
}
```

0.0分

11 人评分

C语言网提供「C语言、C++、算法竞赛、真题百练、Python课程」在线课程，全部由资深研发工程师或ACM金牌大佬亲授课，更科学、全面的课程体系，以在线视频+在线评测的学习模式学习，学练同步，拒绝理论派，真正学会编程！还有奖学金等增值福利等你！

trudbot

TA的其他文章

你可能喜欢

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

简单的a+b （C语言代码）

printf基础练习2 （C语言代码）

C语言训练-自由落体问题（C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

倍增LCA算法

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

Pascal三角（C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

回文数字（C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

企业奖金发放（C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

trudbot

TA的其他文章

你可能喜欢

C语言训练-求具有abcd=(ab+cd)2性质的四位数 （C语言代码）

简单的a+b （C语言代码）

printf基础练习2 （C语言代码）

C语言训练-自由落体问题 （C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

倍增LCA算法

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

Pascal三角 （C语言代码）

C语言考试练习题_一元二次方程 （C语言代码）

回文数字 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

企业奖金发放 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

C语言训练-自由落体问题（C语言代码）

　　评论区

Pascal三角（C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

回文数字（C语言代码）

企业奖金发放（C语言代码）