Finding LCA

// Caution : must b 0 based node ....
void dfs(int v, int pr){
    tin[v] = T++;
    p[0][v] = pr;
    u[v] = true;
    for(int i = 1; i < LOGN; ++i)
        p[i][v] = p[i - 1][ p[i - 1][v] ];

    for(auto e : g[v]){
        int to = e.first, len = e.second;
        if(!u[to]){
            dfs(to, v);
        }
    }

    tout[v] = T;
}

bool isAncestor(int a, int b){
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int getLCA(int a, int b){
    if(isAncestor(a, b)) return a;
    if(isAncestor(b, a)) return b;

    for(int i = LOGN - 1; i >= 0; --i)
        if(!isAncestor(p[i][a], b))
            a = p[i][a];

    return p[0][a];
}