LCA2

이 문제는 쉬움
https://www.acmicpc.net/problem/11438

못풀면 멍청한 사람임

못풀면 공부하고 오세요

코드는 드릴게

#include <iostream>
#include <vector>
#include <cmath>
 
#define swap(a,b){int t = a; a = b; b = t;}
#define maxnode 100002 // 최대 노드개수입니다
 
using namespace std;
 
int depth[maxnode]; // 노드의 위치(깊이)를 저장합니다.
int ac[maxnode][20]; // 노드의 조상들을 저장합니다.
 
 
vector <int> v[maxnode]; // 노드 쌍을 받습니다.
int max_lv = (int)floor(log2(maxnode));
int a, b;
 
// 트리를 만드는 함수입니다.
void getTree(int now, int father) {
    // 자식은 아빠보다 아래 레벨에 있습니다
    depth[now] = depth[father] + 1;
 
    // 현재의 첫 조상(2^0)은 아빠
    ac[now][0] = father;
 
    // 이해하기 쉽게 나누어서 적어둡니다
    // 깊이 1부터 최대 깊이 까지 돌립니다
    // 이 때 현재의 첫 조상부터 조상의 조상들을 세팅해줍니다.
    for (int i = 1; i <= max_lv; i++) {
        int temp = ac[now][i - 1];
        ac[now][i] = ac[temp][i - 1];
    }
 
    // dfs로 들어갑니다.
    // 이 과정을 반복하며 자식들이 root에서 붙어가며 늘어납니다
    int l = v[now].size();
    for (int i = 0; i < l; i++) {
        int k = v[now][i];
        if (k != father)
            getTree(k, now);
    }
}
 
int main()
{
    cin.tie(NULL);
    ios_base::sync_with_stdio(0);
 
    int N;
    cin >> N;
    
    // 양방향 그래프로 만들어 줍니다.
    for (int i = 0; i < N-1; i++) {
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
 
    // 루트노드의 부모는 없습니다
    // 패드립이 아닙니다
    depth[0] = -1;
 
    // 트리를 만들고
    getTree(1, 0);
 
    int M;
    cin >> M;
    // 조건을 찾아 답을 내줍시다
    while (M--) {
        cin >> a >> b;
        // 글을 보고 오셨을것이라 믿고 설명합니다
        // 여기서는 깊이를 비교합니다.
        // 깊이가 같을때까지 깊은곳에서 낮은곳으로 올려주고
        // 그 후 두개 다 하나씩 올려가며 조상을 비교합니다
        if (depth[a] != depth[b]) {
            // 비교가 편하게 스왑을 해주는 겁니다
            if (depth[a] > depth[b])
                swap(a, b);
            // 조상을 높은 차수부터 내려오면서 비교해줍니다.
            for (int i = max_lv; i >= 0; i--) {
                if (depth[a] <= depth[ac[b][i]])
                    b = ac[b][i];
            }
        }
        int lca = a;
 
        // 같지 않다면 같을 때 까지 두들겨 패줍니다
        if (a != b) {
            for (int i = max_lv; i >= 0; i--) {
                if (ac[a][i] != ac[b][i]) {
                    a = ac[a][i];
                    b = ac[b][i];
                }
                lca = ac[a][i];
            }
        }
 
        cout << lca << '\n';
    }
    return 0;
}