蓝桥杯2023（十四届）省赛——景区导游（最近公共祖先LCA）

本文主要是介绍蓝桥杯2023（十四届）省赛——景区导游（最近公共祖先LCA），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

景区导游（最近公共祖先）

1.景区导游 - 蓝桥云课 (lanqiao.cn)

本来一开始想用Floyd算法，看看能不能水个分的，但是实际上，居然运行错误呜呜呜呜。

但是实际上和我一开始分析的是一样的，最近公共祖先。但是我看题解上可以使用dfs暴力搜出来，我想试试。

来总结一下这道题的核心：树中两个节点之间的距离=二者到最近公共祖先的距离之和，所以，我们需要知道最近公共祖先是哪个。这里还有一个妙点就是，通过计算当前位置到根节点的位置计算到最近公共祖先的距离。比如a和b的公共祖先是g，他们的根是r，于是就有：agb=ra+rb-2*rg。

但是这道题和我之前刷的公共祖先不一样的地方在于，不是用并查集的方法，而是用了一个所谓的 倍增法。二维数组 f 用于存储每个节点的祖先节点信息：f[i][j] 表示节点 i 的第 2^j 个祖先节点。例如，f[i][0] 就是节点 i 的直接父节点，f[i][1] 是节点 i 的祖父节点，f[i][2] 是节点 i 的曾祖父节点，以此类推。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;//那既然是用dfs的话，恐怕确实是需要存个图，用邻接表？
//我放弃了，我还是用最近公共祖先吧
//
//难点在于如何快速求两点之间的距离。
// 在树状结构中，两点距离 == 两点到达共同祖先LCA的距离之和。我们可以先预处理出各结点到根节点的距离。
// 然后借助LCA算法求两点的LCA，则两点之间的距离 == 两点到根节点的距离之和 - LCA到根节点的距离 * 2；//这里还用了一个新的东西，跳表法，也就是f[][]。f[i][j]表示节点 i 的第 2^j 个祖先节点
typedef long long LL;
typedef pair<int, int> PII;const int N = 100010;vector<PII> g[N];	//实际上是以边的形式存的图
int f[N][23], d[N];
LL dist[N];
int a[N];
int n, k;void bfs()	//求每个点到根节点的距离
{queue<int>q;q.push(1);d[1] = 1;while (!q.empty()){int cur = q.front();q.pop();for (auto& nex : g[cur]){int nexpos = nex.first;int val = nex.second;if (d[nexpos]!=0)	continue;	//如果已经走过了，直接跳过，防止向上回溯，陷入死循环d[nexpos] = d[cur] + 1;	//这里应该是表示层数dist[nexpos] = dist[cur] + val;	//这里记录的是nexpos到树顶点的距离f[nexpos][0] = cur;	//表示nexpos的直接祖先结点是curfor(int k=1;k<=20;k++)	//这里的20表示最高深度不超过20层，20层已经够用了f[nexpos][k] = f[f[nexpos][k - 1]][k - 1];q.push(nexpos);	//将下一个结点存进去}}
}int lca(int x,int y)	//最近公共祖先
{if (d[x] > d[y])	//如果x更深swap(x, y);	//将深的那方始终置于y//使两节点深度相同：for (int i = 20; i >= 0; i--)	//从深层往低层遍历if (d[f[y][i]] >= d[x])	//如果y的最深的那个祖先（第2^i个祖先）仍然比x层次更深y = f[y][i];		//将y直接跳跃到这个祖先来（相当于连续跳了2^i个）//现在y的所有祖先的深度都比x浅，说明x,y同深度：if (x == y) return x;for (int i = 20; i >= 0; i--)	//找公共祖先if (f[x][i] != f[y][i])		//遍历当前的所有公共祖先，一旦遇到不相同的，那就向上跳，直到二者祖先完全一致x = f[x][i], y = f[y][i];	//同步阀向上遍历//现在f[x][i] == f[y][i],说明二者的祖先已经完全一致了，而最近公共祖先就是f[x][0]，也就是当前父结点return f[x][0];
}int main()
{cin >> n >> k;int u, b, v;for (int i = 0; i < n - 1; i++){cin >> u >> b >> v;g[u].push_back({ b,v });g[b].push_back({ u,v });}bfs();	//计算各个节点到根节点之间的位置for (int i = 1; i <= k; i++)cin >> a[i];LL res = 0;	//这里计算的是原始路径的长度，之后再减去删除的位置所对应的长度即可for (int i = 2; i <= k; i++){LL ans = dist[a[i]] + dist[a[i - 1]] - 2 * dist[lca(a[i], a[i - 1])];//两点之间距离 = 二者到根节点的距离之和 - 2 * 二者最近公共祖先到根节点的距离之和res += ans;}for (int i = 1; i <= k; i++)	//遍历删除的位置{LL sub = 0;//对于开头结尾不走的话，直接减去1~2，k-1~k之间的长度即可if (i == 1)	//特殊情况特殊考虑	sub = dist[a[1]] + dist[a[2]] - 2 * dist[lca(a[1], a[2])];else if (i == k)sub = dist[a[k-1]] + dist[a[k]] - 2 * dist[lca(a[k-1], a[k])];else  //对于中间节点而言，如果不走的话，比如abc不走b，本来是ab+bc，现在需要减去(ab+bc)然后+ac{sub += dist[a[i - 1]] + dist[a[i]] - dist[lca(a[i - 1], a[i])] * 2;	//-absub += dist[a[i]] + dist[a[i + 1]] - dist[lca(a[i], a[i + 1])] * 2;	//-bcsub -= dist[a[i - 1]] + dist[a[i + 1]] - dist[lca(a[i - 1], a[i + 1])] * 2;	//+ac}cout << res - sub << " ";}return 0;
}

二刷出现的问题：

注意最后一步找公共祖先的时候：

for (int i = 20; i >= 0; i--)	//找公共祖先if (f[x][i] != f[y][i])		//遍历当前的所有公共祖先，一旦遇到不相同的，那就向上跳，直到二者祖先完全一致x = f[x][i], y = f[y][i];	//同步阀向上遍历

这里的i是需要 >=0 的，因为我们最后返回的最近公共祖先是x，y的父亲节点，所以他们的父亲节点也应该要一样才可以。

三刷：

**一定要开long long，一定要开long long！**思路和之前刷的差不多，可能代码细节上有些区别，大家可以选择自己好理解的方式~

//景区导游
#include <iostream>
#include <queue>
#include <vector>
#include <map>
using namespace std;
#define ll long long
#define PII pair<int,int>
const int N=1e5+3;ll n,k;
vector<vector<PII> >g(N);
ll f[N][23]={0};
//int book[N]={0};	//其实不需要book来标记，deep可以两用 
ll dist[N]={0};	//表示i结点到 1 的距离 
ll deep[N]={0};
ll plan[N]={0};void bfs()
{queue<ll>q;q.push(1);deep[1]=1;while(!q.empty()){ll cur=q.front();q.pop();for(auto it:g[cur]){int nex=it.first;int val=it.second;if(deep[nex]!=0)	continue;dist[nex]=dist[cur]+val;f[nex][0]=cur;deep[nex]=deep[cur]+1;q.push(nex);for(int i=1;i<=20;i++)	//这里要打满20层，之前1~19层就不行，改到20层就OK了 f[nex][i]=f[f[nex][i-1]][i-1];}}
}ll lca(ll a,ll b)
{if(deep[a]>deep[b])	swap(a,b);	//把深的给bfor(int i=20;i>=0;i--)if(deep[f[b][i]]>=deep[a]) //如果存在b的祖先深度比a的还深，那直接跳b=f[b][i];//现在a,b持平了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 getDist(int a,int b)
{return dist[a]+dist[b]-2*dist[lca(a,b)];
}int main()
{cin>>n>>k;int a,b,v;for(int i=1;i<n;i++){cin>>a>>b>>v; g[a].push_back({b,v});g[b].push_back({a,v});}bfs();ll sum=0; for(ll i=0;i<k;i++){cin>>plan[i];if(i!=0)	sum+=getDist(plan[i-1],plan[i]);}ll ans=0;for(ll i=0;i<k;i++)	//依次删除{if(i==0)ans=sum-getDist(plan[0],plan[1]);else if(i==k-1)ans=sum-getDist(plan[k-2],plan[k-1]);else ans=sum-getDist(plan[i-1],plan[i])-getDist(plan[i],plan[i+1])+getDist(plan[i-1],plan[i+1]);cout<<ans<<" ";} return 0;}