LCA to RMQ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class LCA {

    static ArrayList<Integer>[] adj;
    static int[] e, l, h, tree;
    static int idx;

    static void dfs(int i, int lvl, int p) {
        e[idx] = i;
        l[idx++] = lvl;
        if (h[i] == -1)
            h[i] = idx - 1;
        for (Integer v : adj[i]) {
            if (v == p)
                continue;
            dfs(v, lvl + 1, i);
            e[idx] = i;
            l[idx++] = lvl;
        }
    }

    static void build(int idx, int s, int t) {
        if (s == t) {
            tree[idx] = s;
            return;
        }
        int mid = (s + t) / 2;
        build(idx * 2, s, mid);
        build(idx * 2 + 1, mid + 1, t);
        int val1 = l[tree[idx * 2]];
        int val2 = l[tree[idx * 2 + 1]];
        if (val1 < val2)
            tree[idx] = tree[idx * 2];
        else
            tree[idx] = tree[idx * 2 + 1];
    }

    static int rqst(int idx, int s, int t, int i, int j) {
        if (t < i || s > j)
            return Integer.MAX_VALUE;
        if (s >= i && t <= j)
            return tree[idx];
        int mid = (s + t) / 2;
        int idx1 = rqst(idx * 2, s, mid, i, j);
        int idx2 = rqst(idx * 2 + 1, mid + 1, t, i, j);
        if (idx1 == Integer.MAX_VALUE)
            return idx2;
        if (idx2 == Integer.MAX_VALUE)
            return idx1;
        int val1 = l[idx1];
        int val2 = l[idx2];
        if (val1 < val2)
            return idx1;
        return idx2;
    }

    @SuppressWarnings("unchecked")
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        sc = new StringTokenizer("");
        adj = new ArrayList[13];
        for (int i = 0; i < 13; i++)
            adj[i] = new ArrayList<>();
        e = new int[25];
        l = new int[25];
        h = new int[13];
        for (int i = 0; i < 12; i++) {
            int x = nxtInt() - 1;
            int y = nxtInt() - 1;
            adj[x].add(y);
            adj[y].add(x);
        }
        Arrays.fill(h, -1);
        dfs(0, 0, -1);
        for (int i = 0; i < e.length; i++) {
            out.print(e[i] + 1 + " ");
        }
        out.println();
        for (int i = 0; i < l.length; i++) {
            out.print(l[i] + " ");
        }
        out.println();
        for (int i = 0; i < h.length; i++) {
            out.print(h[i] + 1 + " ");
        }
        out.println();
        tree = new int[4 * 25];
        build(1, 0, l.length - 1);
        while (true) {
            int x = nxtInt();
            int y = nxtInt();
            if (x == y && x == -1)
                break;
            int val1 = h[x - 1];
            int val2 = h[y - 1];
            if (val1 > val2) {
                val1 ^= val2;
                val2 ^= val1;
                val1 ^= val2;
            }
            int ans = rqst(1, 0, l.length - 1, val1, val2);
            out.println(e[ans] + 1);
        }
        br.close();
        out.close();
    }

    static BufferedReader br;
    static StringTokenizer sc;
    static PrintWriter out;

    static String nxtTok() throws IOException {
        while (!sc.hasMoreTokens()) {
            String s = br.readLine();
            if (s == null)
                return null;
            sc = new StringTokenizer(s.trim());
        }
        return sc.nextToken();
    }

    static int nxtInt() throws IOException {
        return Integer.parseInt(nxtTok());
    }

    static long nxtLng() throws IOException {
        return Long.parseLong(nxtTok());
    }

    static double nxtDbl() throws IOException {
        return Double.parseDouble(nxtTok());
    }

    static int[] nxtIntArr(int n) throws IOException {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = nxtInt();
        return a;
    }

    static long[] nxtLngArr(int n) throws IOException {
        long[] a = new long[n];
        for (int i = 0; i < n; i++)
            a[i] = nxtLng();
        return a;
    }

    static char[] nxtCharArr() throws IOException {
        return nxtTok().toCharArray();
    }
}