http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4313940#1

main.d

import std.stdio, std.string, std.algorithm, std.array, std.range, std.conv,
    std.typecons, std.math, std.container, std.format, std.numeric;

long[] parent;
long[][] children;
long[] depth;
long[][] ancestor_table;

void calc_depth(long i, long d)
{
    depth[i] = d;
    foreach (c; children[i])
    {
        calc_depth(c, d + 1);
    }
}

void make_table(long n, long size)
{
    foreach (i; 0 .. size)
    {
        foreach (j; 0 .. n)
        {
            if (i == 0)
            {
                ancestor_table[j][i] = parent[j];
            }
            else
            {
                auto k = ancestor_table[j][i - 1];
                if (k == -1)
                {
                    ancestor_table[j][i] = -1;
                }
                else
                {
                    ancestor_table[j][i] = ancestor_table[k][i - 1];
                }
            }
        }
    }
}

long get_nth_parent(long p, long n)
{
    long i = 0;
    while (n != 0 && p != -1)
    {
        if (n & 1)
        {
            p = ancestor_table[p][i];
        }
        i++;
        n /= 2;
    }
    return p;
}

long lca(long u, long v, long n)
{
    if (depth[u] > depth[v])
    {
        swap(u, v);
    }

    v = get_nth_parent(v, depth[v] - depth[u]);
    assert(depth[u] == depth[v]);
    // long ok = 0;
    // while (get_nth_parent(u, ok) != get_nth_parent(v, ok))
    // {
    //     ok++;
    // }
    // return get_nth_parent(u, ok);

    long ok = depth[v], ng = -1;
    while (abs(ng - ok) > 1)
    {
        long m = (ok + ng) / 2;
        if (get_nth_parent(u, m) == get_nth_parent(v, m))
        {
            ok = m;
        }
        else
        {
            ng = m;
        }
    }

    return get_nth_parent(v, ok);
}

void main(string[] args)
{
    long n;
    readf("%d\n", &n);
    parent = new long[](n);
    children = new long[][](n);

    parent.fill(-1);
    foreach (i; 0 .. n)
    {
        auto cs = readln.strip.split(" ").to!(long[]);
        foreach (c; cs[1 .. $])
        {
            parent[c] = i;
            children[i] ~= c;
        }
    }

    depth = new long[](n);
    calc_depth(0, 0);

    long size = 0;
    for (long i = 1; i < n; i *= 2)
    {
        size++;
    }

    ancestor_table = new long[][](n, size);
    make_table(n, size);

    long q;
    readf("%d\n", &q);
    long u, v;
    foreach (i; 0 .. q)
    {
        readf("%d %d\n", &u, &v);
        long ans = lca(u, v, n);
        writeln(ans);
    }
}