~~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.