<—点个赞吧QwQ
宣传一下算法提高课整理{:target=”_blank”}
倍增
对于树结构中的任意两个节点$s$和$e$,它们的位置关系有以下三种:
1、$s$在以$e$的子树中
2、$e$在以$s$的子树中
3、$s$,$e$在第三个节点$a$的不同子树中
对于情况1,2,向上标记和向下标记都可,但对于情况3,就只能向上标记了,此外,由于问题中最大节点数为4万,向上标记必须用更高效的方式,由于任何数都可以拆分成2的正整数次幂的和,故向上标记的过程可以用倍增的方法
由于构造的树结构是无向的,我们必须用深度来人为规定每条边的方向,求出深度的同时,还需要用倍增法记录上移之后到达的节点,这里使用二维数组pre记录,$pre[i][j]$表示从节点$i$开始,向上移动$2^j$层之后到达的节点序号
构造pre表时,移动$2^j$层可以拆分成先后两次移动,每次分别移动$2^{j-1}$层,得到递推关系:
$$ pre[i][j] = pre[pre[i][j-1]][j-1] $$
然后根据pre表来求lca,这时也不用分三种情况了,统一由深度大的节点$s$向深度小的节点$e$收束,两个节点的深度差可以由指数从大到小进行二进制划分,然后以此向上分步移动相应的层数,直到两节点同层,此时$s$可以等于也可以不等于$e$,如果等于,直接返回$s$,如果不等于,就将$s$和$e$的深度再次进行二进制划分,然后同时按照指数从大到小向上移动,直到两者收束,既前驱节点相同,这时返回值就是$s$的前驱节点
详情和细节请见注释
时间复杂度
$O((n+m)*log(n))$,n是节点数,m是查询次数
C++ 代码
#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <functional>
#include <queue>
using namespace std;
const int N = 4e4 + 5, M = 2 * N, P = 16;
int n, m, s, e, tot = 2, root = 0;
int fin[M], last[N], nxt[M], depth[N], pre[N][P];
//pre[i][j]的意思是节点i向上移动2^j层后到达的节点序号(出界了就标记为0)
queue<int> q;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
function<void(int, int)> _connect = [=](int s, int e)->void {
fin[tot] = e;
nxt[tot] = last[s];
last[s] = tot++;
};
function<void(int, int)> connect = [=](int s, int e)->void {
_connect(s, e);
_connect(e, s);
};
cin >> n;
//确定根节点
for (int i = 0; i < n; i++) {
cin >> s >> e;
if (e == -1) root = s;
else connect(s, e);
}
//初始化深度,确定搜索的方向性,同时初始化pre表
fill(depth + 1, depth + N, 1e9 + 7);
depth[root] = 1;
q.push(root);
while (!q.empty()) {
int cur = q.front();
q.pop();
for (int i = last[cur]; i != 0; i = nxt[i]) {
int nx = fin[i];
if (depth[nx] > depth[cur] + 1) {
depth[nx] = depth[cur] + 1;
q.push(nx);
//向上移动1层,就是前驱节点
pre[nx][0] = cur;
//向上移动2^j层,可以理解为先移动2^(j-1)层,然后从该节点开始再向上移动2^(j-1)层
for (int j = 1; j < P; j++) pre[nx][j] = pre[pre[nx][j - 1]][j - 1];
}
}
}
function<int(int, int)> lca = [=](int s, int e)-> int {、
//默认s比e深度大
if (depth[s] < depth[e]) swap(s, e);
//只要深度不比e小,就让s倍增的向上移动
for (int i = P - 1; i >= 0; i--) {
if (depth[pre[s][i]] >= depth[e]) s = pre[s][i];
}
//出循环后s和e的深度一定是相同的,如果s=e,就可以直接出结果了
if (s == e) return s;
//如果s,e不相等,那就继续让s,e倍增上移,直至收束
for (int i = P - 1; i >= 0; i--) {
//这里体现了出界置0的好处,如果上移出界,两者都为0,不会更新s,e的位置
if (pre[s][i] != pre[e][i]) {
s = pre[s][i];
e = pre[e][i];
}
}
//由于s,e深度相同,它俩一定会收束到某个节点,这个节点就是循环结束后s的前驱节点
return pre[s][0];
};
cin >> m;
while (m--) {
cin >> s >> e;
if (lca(s, e) == s) cout << 1 << endl;
else if (lca(s, e) == e) cout << 2 << endl;
else cout << 0 << endl;
}
return 0;
}