LCA HL分解

heavy light decompositionを試したのでLCAの問題にsubmit。
参考にした資料
http://math314.hateblo.jp/entry/2014/06/24/220107

問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C

#include<iostream>
#include<vector>
#include<algorithm>

#define REP(i, n) for (int i=0;i<int(n);++i)
#define EACH(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(A) A.begin(), A.end()

using namespace std;

struct HeavyLight {
  int pathCount,n;
  vector<int>size,parent,in,out,path,pathRoot;
  vector<vector<int> > tree;

  HeavyLight(vector<vector<int> > t)
    :pathCount(0),n(t.size()),size(n),parent(n),in(n),out(n),
     path(n),pathRoot(n),tree(t){
    int time=0;
    dfs(0,-1,time);
    buildPaths(0,newPath(0));
  }

  void dfs(int u, int p, int &k){
    in[u]=k++, parent[u]=p, size[u]=1;
    EACH(v,tree[u])if(*v!=p)dfs(*v, u, k),size[u]+=size[*v];
    out[u]=k++;
  }

  int newPath(int u){ pathRoot[pathCount]=u; return pathCount++; }

  void buildPaths(int u, int pt){
    path[u]=pt;
    EACH(v,tree[u])if(*v != parent[u])
      buildPaths(*v, 2*size[*v] >= size[u] ? pt : newPath(*v));
  }

  bool isAncestor(int p, int ch){
    return in[p] <= in[ch] && out[ch] <= out[p];
  }

  int lca(int a,int b){
    for(int root; !isAncestor(root=pathRoot[path[a]],b);a=parent[root]);
    for(int root; !isAncestor(root=pathRoot[path[b]],a);b=parent[root]);
    return isAncestor(a,b)?a:b;
  }
};

int main(void){
  ios::sync_with_stdio(false);

  int n;
  cin >> n;
  vector<vector<int> >tree(n);
  
  REP(i,n){
    int k;
    cin >> k;
    REP(j,k){
      int ch;
      cin >> ch;
      tree[i].push_back(ch);
    }
  }

  HeavyLight hl = HeavyLight(tree);

  int q;
  cin >> q;
  while(q--){
    int u,v;
    cin >> u >> v;
    cout << hl.lca(u,v) << "\n";
  }
  
  return 0;
}