알고리즘/BOJ

[BOJ 15480] LCA와 쿼리

IKnoom 2020. 4. 24. 23:13

https://www.acmicpc.net/problem/15480

 

15480번: LCA와 쿼리

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리 T의 간선 정보 u와 v가 주어지다. u와 v는 트리의 간선을 나타내는 두 정점이다. 다음 줄에는 쿼리의 개수 M(1 ≤ M ≤ 100,000)가 주어진다. 다음 M개의 줄에는 쿼리를 나타내는 r, u, v가 주어진다.

www.acmicpc.net

 

만약 기존에 LCA2를 풀어봤다면 딱 case만 분류하면 끝이다.

 

 

    while (Q--) {
        int u, v, r;
        cin >> u >> v >> r;
        u -= 1; v -= 1; r -= 1;
        int c = LCA(u, v);

        if (LCA(c, r) != c) {
            cout << c + 1 << '\n';
        } else {
            int k = LCA(u, r);
            if (k != c) cout << k + 1 << '\n';
            else cout << LCA(v, r) + 1 << '\n';
        }
    }