RootedTree.cpp

struct rootedtree{
    int V;
    vector<vector<int> > T;
    vector<vector<int> > parents;
    vector<int> depth;
    int log_N = 20;

    rootedtree(int N, vector<vector<int> > &Tree){
        V = N;
        T = Tree;

        depth = vector<int>(V,0);
        parents = vector<vector<int> >(V, vector<int>(log_N-1,0));
        dfs(0,-1,0);

        FOR(i,0,log_N-1){
            FOR(j,0,V){
                if(parents[j][i] == -1)
                    parents[j][i+1] = -1;
                else
                    parents[j][i+1] = parents[parents[j][i]][i];
            }
        }
    }

    void dfs(int u,int parent,int d){
        depth[u] = d;
        parents[u][0] = parent;
        for(int v : T[u]){
            if(v != parent)
                dfs(v, u, d + 1);
        }
    }

    int lca(int u, int v){
        if(depth[v] < depth[u])
            swap(u,v);
         
        for(int i=log_N-1;i>=0;i--){
            if(((depth[v] - depth[u])>>i)&1)
                v = parents[v][i];
         }

        if(u==v) return u;

        for(int i=log_N-1;i>=0;i--){
            if(parents[u][i] != parents[v][i]){
                u = parents[u][i];
                v = parents[v][i];
            }
        }
        
        return parents[u][0];
    }

    int dist(int u, int v){
        int l = lca(u,v);
        return (depth[u] - depth[l]) + (depth[v] - depth[l]);
    }
};