LCA(Lowest Common Ancestor)

#include<iostream>
#include<vector>
 
using namespace std;
 
vector<vector<int>> tree;    //tree[i] : i 번 노드가 가지는 자식들의 목록
vector<vector<int>> par;    //par[node][i] : node의 2^i 번째 부모의 번호, par[node][i] = par[par[node][i-1]][i-1]
vector<int> depths;            //depths[i] : i번째 노드의 깊이(root의 깊이는 0 이다)
 
void DFS(int node, int dep) {
    depths[node] = dep;
    int cDepth = 1;
    int tmp, i = 1;
    while (dep >= cDepth) {
        par[node][i] = par[par[node][i - 1]][i - 1];
        i++;
        cDepth *= 2;
    }
 
    for (int i = 0; i < tree[node].size(); i++) {
        DFS(tree[node][i], dep + 1);
    }
}
 
int LCA(int a, int b) {
    //a와 b를 같은 깊이가 되도록 한다.
    int low, deep;
    if (depths[a] < depths[b])
        low = a, deep = b;
    else
        low = b, deep = a;
 
    int diff = depths[deep] - depths[low];
 
    //deep의 위치를 diff만큼 끌어올려서 low와 같게한다.
    int i = 0;
    while (1) {
        if (diff == 0)
            break;
        if ((diff & 1) != 0)
            deep = par[deep][i];
 
        diff = diff >> 1;
        i++;
    }
 
    //low와 deep 번호의 최소 공통조상을 구한다.
    
    if (low == deep)
        return low;
    
    int index = 1;
    while (par[low][0] != par[deep][0]) {
        while (par[low][index] != par[deep][index])
            index++;
        index--;
        low = par[low][index];
        deep = par[deep][index];
    }
 
    return par[low][0];
}
 
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int N;
    cin >> N;
 
    tree.assign(N, vector<int>());
    par.assign(N, vector<int>(N, -1));
    depths.assign(N, -1);
    int input;
 
    for (int i = 1; i < N; i++) {
        cin >> input;
        //i의 직계부모는 input이다.
        par[i][0] = input;
        tree[input].push_back(i);
    }
 
    DFS(0, 0);
    int ret = LCA(5, 10);
    ret = LCA(1, 13);
    ret = LCA(7, 10);
    ret = LCA(13, 6);
    ret = LCA(1, 1);
    ret = LCA(2, 27);
    ret = LCA(5, 14);
 
    return 0;
}
 
 
/*
19
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
31
0 0
1 1 2 2
3 3 4 4 5 5 6 6
7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14
*/