LCA

int depth[MAX];
int parent[MAX][18];

void dfs(int v = 1, int par = 0, int h = 1){
    depth[v] = h;
    parent[v][0] = par;
    for(int i = 1; i < 18; i++){
        parent[v][i] = parent[parent[v][i-1]][i-1];
    }
    for(int &it: g[v]){
        if(it != par)dfs(it,v,h+1);
    }
}

int LCA(int a, int b){
    if(depth[a] < depth[b])
        swap(a,b);
    int k = depth[a]-depth[b];
    for(int i = 17; i >= 0; i--){
        if(k&(1<<i)){
          a = parent[a][i];
        }
    }
    if(a == b)return a;
    for(int i = 17; i >= 0; i--){
        if(parent[a][i] != parent[b][i]){
            a = parent[a][i];
            b = parent[b][i];
        }
    }
    return parent[a][0];
}