蓝桥杯2022年第十三届决赛C++ B组真题-机房
比赛的时候还没学到算法提高课的LCA，这题板子题没写出来，难受啊，不然可能就国一了。
:earth_africa: 题目
:lollipop: 思路（LCA)
本题中我们要求的是多源最短路，而且数据量很大，所以平常写的的dijkstra，floyd求最短路都是过不了的。所以这题要用LCA的Tarjan算法来求两个点的最短路。
LCA的Tarjan算法
- 在线做法：读一个询问，处理一个，输出一个
- 离线做法：读完全部询问，再全部处理完，再全部输出
Tarjan是一种离线算法，是对向上标记法的一种优化，我们向上标记的时候是一个一个向上走的，效率低，而tarjian可以优化到O(1)的复杂度。
在深度优先遍历时，数种的节点分为三类：
- 2号点： 已经访问完毕并且回溯过的点。
- 1号点：已经开始递归，但还没有回溯的点。也就是正在访问的节点以及他的所有祖先。
- 0号点：尚未访问的点
为什么要这样做呢？我们可以发现，对于1号点而言，所有的二号点的祖先都是1号点，也就是他们的lca，这也就是树上标记法中一个点向上走遇到的第一个标记的节点。那么怎么快速找到2号点祖先对对应的1号点呢？这里可以云并查集进行优化，1号点的分支中所有的2号点都是以1号点为祖先。当一个节点是2号点后，把它所在的集合合并到它的父节点所在的集合中（此时父节点一定是1号点）
这样每个完成回溯的点都有一个指针指向了它的父节点，只需查询y所在集合的代表元素，就等价于从y向上走一直走到一个开始递归但尚未回溯的点，即lca(x,y)
如下图：红色点表示2号点，蓝色点表示1号点，白色点表示0号点
对了本题中，我们需要记录每个点到根节点的距离，那么求两个点u和v的距离就等于dist[u] + dist[v] - 2 * dist[lca(a,b)] + w[lca(a,b)] (w数组表示每个点的权值)。比如上图中的4号点和5号点的距离，dist[4] = w[1] + w[2] + w[4],dist[5] = w[1] + w[2] + w[5]，dist[2] = w[1] + w[2]。
所以就可以表示成dist[4] + dist[5] - 2 * dist[2] + w[2]
:horse: AC代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 1e5 + 10, M = N * 2;
int n, m;
int h[N], e[M], ne[M], idx; //邻接表
int w[N]; //每个点的权值
int dist[N]; //根节点到每个点的权值和
int ans[N]; //每个询问的答案
int p[N]; // 并查集数组
int st[N]; //每个点的状态
vector<PII> query[N]; //存每个询问
void add(int a, int b) // 添加一条边a->b
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int find(int x)
{
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
void dfs(int u, int fa, int sum)
{
dist[u] = sum;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (j == fa)
continue;
dfs(j, u, sum + w[j]);
}
}
void tarjan(int u)
{
//正在递归的点，但还没回溯
st[u] = 1;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (st[j])
continue;
tarjan(j);
p[j] = u;
}
for (int i = 0; i < query[u].size(); i++)
{
int v = query[u][i].x;
int id = query[u][i].y;
int anc = find(v);
if (st[v] == 2)
ans[id] = dist[u] + dist[v] - dist[anc] * 2 + w[anc];
}
//递归完回溯回去
st[u] = 2;
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m;
//初始化并查集数组
for (int i = 1; i <= n; i++)
p[i] = i;
for (int i = 0; i < n - 1; i++)
{
int a, b;
cin >> a >> b;
add(a, b);
add(b, a);
//每个点的权值+1
w[a]++;
w[b]++;
}
for (int i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
if (a == b) //这里要特判，如果两个点相同，那么可以直接得到结果
{
ans[i] = w[a];
continue;
}
query[a].push_back({b, i});
query[b].push_back({a, i});
}
//求dist数组
dfs(1, -1, w[1]);
//核心：求最短路径
tarjan(1);
for (int i = 1; i <= m; i++)
cout << ans[i] << '\n';
return 0;
}
:star: 有疑问欢迎评论区留言哦
:lollipop: 帮到您的话欢迎点个赞再走啊
