Lca Java

  ArrayList<Integer>[] g;
  int n, l;
  int tin[], tout[];
  int timer;
  int up[][];

  void dfs (int v, int p) {
    tin[v] = ++timer;
    up[v][0] = p;
    for (int i=1; i&lt;=l; ++i)
      up[v][i] = up[up[v][i-1]][i-1];
    for (int i = 0; i &lt; g[v].size(); i++) {
      int to = g[v].get(i);
      if (to != p)
        dfs(to, v);
    }
    tout[v] = ++timer;
  }

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

  int lca (int a, int b) {
    if (upper (a, b))  return a;
    if (upper (b, a))  return b;
    for (int i=l; i&gt;=0; --i)
      if (! upper (up[a][i], b))
    a = up[a][i];
    return up[a][0];
  }

  void solve() {
    g = new ArrayList[n];
    for (int i = 0; i &lt; n; i++)
      g[i] = new ArrayList <Integer>();
    tin = new int[n];
    tout = new int[n];
    up = new int[n][];
    l = 1;
    while ((1 << l) <= n) ++l;
    for (int i = 0; i < n; i++)
      up[i] = new int[l + 1];
    dfs(0, 0);
    // code here:

  }