aisuneko/blog

Posted 2020/09/102 minutes read (About 307 words)

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

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

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

刚好发现一种朴素解法:

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

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

#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;
}