Company Queries II

import java.io.IOException;
import java.io.InputStream;

public class CompanyQueriesII {

    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0;
        private int len = 0;

        FastScanner(InputStream in) {
            this.in = in;
        }

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;

                if (len <= 0) {
                    return -1;
                }
            }
            return buffer[ptr++];
        }

        int nextInt() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);

            int value = 0;

            while (c > ' ') {
                value = value * 10 + c - '0';
                c = read();
            }

            return value;
        }
    }

    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner(System.in);

        int n = input.nextInt();
        int q = input.nextInt();

        int LOG = 1;
        while ((1 << LOG) <= n) {
            LOG++;
        }

        int[][] up = new int[LOG][n + 1];
        int[] depth = new int[n + 1];

        for (int i = 2; i <= n; i++) {
            int boss = input.nextInt();
            up[0][i] = boss;
            depth[i] = depth[boss] + 1;
        }

        for (int j = 1; j < LOG; j++) {
            for (int i = 1; i <= n; i++) {
                up[j][i] = up[j - 1][up[j - 1][i]];
            }
        }

        StringBuilder output = new StringBuilder();

        while (q-- > 0) {
            int a = input.nextInt();
            int b = input.nextInt();

            if (depth[a] < depth[b]) {
                int temp = a;
                a = b;
                b = temp;
            }

            int diff = depth[a] - depth[b];

            for (int j = 0; j < LOG; j++) {
                if ((diff & (1 << j)) != 0) {
                    a = up[j][a];
                }
            }

            if (a == b) {
                output.append(a).append('\n');
                continue;
            }

            for (int j = LOG - 1; j >= 0; j--) {
                if (up[j][a] != up[j][b]) {
                    a = up[j][a];
                    b = up[j][b];
                }
            }

            output.append(up[0][a]).append('\n');
        }

        System.out.print(output);
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED