문제

N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.

두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

입력

첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.

출력

M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.

내 풀이

저번 글에서 풀었던 최소 공통 조상과 같은 맥락의 문제이다. 이번 문제는 루트가 주어지지만 각 노드간의 부모자식 관계는 주어지지 않기 때문에, 노드를 연결리스트에 저장할 때 서로 연결되도록 저장 한 후, 주어진 루트(1) 부터 부모자식 관계를 만들어주면(parent[]) 트리를 만들 수 있다.

이 상태에서 LCA()를 시행해주면 된다.

배운점

저번문제와 연계해서 트리 안에서 LCA를 찾기 위해선 해당 트리의 부모자식 관계와 루트, 두가지 정보를 모두 알고 있어야 LCA를 찾을 수 있음을 배웠다.

소스코드

#include <bits/stdc++.h>
#define ll long long 
using namespace std;

int N, M;
vector<vector<int>> grape(50005, vector<int>());
vector<int> parent(50005, 0), level(50005, 0);


void init(){
    cin >> N;
    int node1, node2;
    for(int i = 0; i < N - 1; i++){
        cin >> node1 >> node2;
        grape[node1].push_back(node2);
        grape[node2].push_back(node1);
    }
}

void set_tree(int node, int pnode){
    parent[node] = pnode;
    level[node] = level[pnode] + 1;
    for(int i = 0; i < grape[node].size(); i++){
        int child = grape[node][i];
        if(child == pnode) continue;
        set_tree(child, node);
    }
}

int lca(int node1, int node2){
    if(level[node1] < level[node2]) return lca(node2, node1);
    while(level[node1] != level[node2]){
        node1 = parent[node1];
    }

    while(node1 != node2){
        node1 = parent[node1];
        node2 = parent[node2];
    }
    return node1;
}

void sol(){
    cin >> M;
    int node1, node2;
    for(int i = 0; i < M; i++){
        cin >> node1 >> node2;
        cout << lca(node1, node2) << "\n";
    }
}


int main(){
    ios_base :: sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
    init();
    set_tree(1, 0);
    sol();

    return 0;
}