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

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

P9245 题解

首先，看到路线构成了一棵树，并且要求两点之间的距离，明显的 LCA 的题。再看一下数据范围：

100000

，符合 LCA 的时间复杂度，就可以用倍增来求。再看下细节。

由于每条路带有权值，想到可以在求 LCA 是用前缀和来维护。用链式前向星存图，定义

dis[i]

代表点

i

距离根节点的边权之和。维护如下：

CPP


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

之间的最短路径：

CPP

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

的情况。

代码如下：

CPP

#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;
}

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

文章操作

P9245 题解

注意：

代码如下：

相关推荐

评论

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