hld lca :O

int sz[MX], in[MX], out[MX], head[MX], dep[MX], par[MX], ind = 0;

void dfs(int x, int p){
    sz[x] = 1;
    dep[x] = dep[p] + 1;
    par[x] = p;
    for(auto &i : adj[x]){
        if(i == p) continue;
        dfs(i, x);
        sz[x] += sz[i];
        if(adj[x][0] == p || sz[i] > sz[adj[x][0]]) swap(adj[x][0], i);
    }
}

void dfs2(int x, int p){
    in[x] = ind++;
    for(auto &i : adj[x]){
        if(i == p) continue;
        head[i] = (i == adj[x][0] ? head[x] : i);
        dfs2(i, x);
    }
    out[x] = ind;
}

int lca(int a, int b){
    while(head[a] != head[b]){
        if(dep[head[a]] > dep[head[b]]) swap(a, b);
        b = par[head[b]];
    }
    if(dep[a] > dep[b]) swap(a, b);
    return a;
}

int main(){

    dfs(1, 0);
    head[1] = 1;
    dfs2(1, 0);

    return 0;
}