SP14932 LCA-Lowest Common Ancestor 超水题解

~~OI生涯中的第一篇题解 ~~

复习LCA的时候去查了查有什么题, 就发现了这道模板题.

因为我太菜, 不会写树上倍增, 就想有什么别的方法能过.

刚好发现一种朴素解法:

  • 先从 x 往上走到根,沿途会经过 x 所有的祖先,把它们用一个数组标记。
  • 再从 y 往上走到根,沿途会经过 y 所有的祖先,遇到的第一个被标记的点就是 x,y 的最近公共祖先。

看了一眼数据范围, N <= 1000. 这么水 (虽然有多组数据), 果断开搞.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <cstring>
using namespace std;
int fa[1005], vis[1005];
int LCA(int x, int y){
memset(vis, 0, sizeof(vis));
while(x!=0){
vis[x]=1;
x=fa[x];
}
while(vis[y]==0){
y=fa[y];
}
return y;
}
int main(){
int T, cnt = 0;
cin >> T;
while(T--){
cnt++;
cout << "Case " << cnt << ":" << endl;
int n;
cin >> n;
for(int i = 1; i <= n; i++){
int m;
cin >> m;
for(int j = 1; j <= m; j++){
int tmp;
cin >> tmp;
fa[tmp] = i;
}
}
int Q;
cin >> Q;
while(Q--){
int a, b;
cin >> a >> b;
cout << LCA(a, b) << endl;
}
}
return 0;
}

没想到竟然AC了……

虽然正解树上倍增肯定要学习一个, 但这也不失为一种骗分~~~~暴力可行的技巧 (如果真的忘了怎么写).

#EOF.