BOJ. Road Network (3176)

[Link] https://www.acmicpc.net/problem/3176

Root the tree at vertex 1 with an explicit stack, recording each vertex’s depth, immediate parent, and the minimum and maximum edge weight on its one-edge climb. For each higher power of two, combine two half-length climbs to build the ancestor, minimum-edge, and maximum-edge tables. The root is its own ancestor; sentinel extrema on its empty climb do not affect any real path.

For a query, first lift the deeper endpoint until both endpoints have equal depth, folding the traversed edge extrema into the answer. Then lift both endpoints together from the largest jump down whenever their ancestors differ, folding both traversals. The remaining one-edge climbs meet at their lowest common ancestor. If both endpoints are the same vertex, the path has no edges; this implementation defines its neutral result as 0 0 (the original constraints generally use distinct endpoints).

The iterative rooting avoids call-stack overflow on a chain of 100,000 vertices. Preprocessing time and storage are O(N log N); each path query takes O(log N) time.

import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.ArrayList;

public class Main {
    static class FastScanner {
        private final BufferedInputStream input = new BufferedInputStream(System.in);
        private final byte[] buffer = new byte[1 << 16];
        private int position;
        private int limit;

        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;
        }

        private int read() throws IOException {
            if (position == limit) {
                limit = input.read(buffer);
                position = 0;
                if (limit == -1) return -1;
            }
            return buffer[position++];
        }
    }

    static class Edge {
        int to;
        int weight;

        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner();
        int n = input.nextInt();
        int levels = 32 - Integer.numberOfLeadingZeros(n);
        ArrayList<Edge>[] graph = new ArrayList[n];
        for (int vertex = 0; vertex < n; vertex++) graph[vertex] = new ArrayList<>();

        for (int i = 0; i < n - 1; i++) {
            int a = input.nextInt() - 1;
            int b = input.nextInt() - 1;
            int weight = input.nextInt();
            graph[a].add(new Edge(b, weight));
            graph[b].add(new Edge(a, weight));
        }

        int[][] up = new int[n][levels];
        int[][] minEdge = new int[n][levels];
        int[][] maxEdge = new int[n][levels];
        int[] depth = new int[n];
        boolean[] visited = new boolean[n];
        int[] stack = new int[n];
        int size = 0;
        stack[size++] = 0;
        visited[0] = true;
        up[0][0] = 0;
        minEdge[0][0] = Integer.MAX_VALUE;
        maxEdge[0][0] = Integer.MIN_VALUE;

        while (size > 0) {
            int vertex = stack[--size];
            for (Edge edge : graph[vertex]) {
                if (visited[edge.to]) continue;
                visited[edge.to] = true;
                up[edge.to][0] = vertex;
                minEdge[edge.to][0] = edge.weight;
                maxEdge[edge.to][0] = edge.weight;
                depth[edge.to] = depth[vertex] + 1;
                stack[size++] = edge.to;
            }
        }

        for (int j = 1; j < levels; j++) {
            for (int vertex = 0; vertex < n; vertex++) {
                int middle = up[vertex][j - 1];
                up[vertex][j] = up[middle][j - 1];
                minEdge[vertex][j] = Math.min(minEdge[vertex][j - 1], minEdge[middle][j - 1]);
                maxEdge[vertex][j] = Math.max(maxEdge[vertex][j - 1], maxEdge[middle][j - 1]);
            }
        }

        int queryCount = input.nextInt();
        StringBuilder output = new StringBuilder();
        for (int query = 0; query < queryCount; query++) {
            int a = input.nextInt() - 1;
            int b = input.nextInt() - 1;
            if (a == b) {
                output.append("0 0\n");
                continue;
            }

            int min = Integer.MAX_VALUE;
            int max = Integer.MIN_VALUE;
            if (depth[a] < depth[b]) {
                int temp = a;
                a = b;
                b = temp;
            }

            int difference = depth[a] - depth[b];
            for (int j = levels - 1; j >= 0; j--) {
                if ((difference & (1 << j)) != 0) {
                    min = Math.min(min, minEdge[a][j]);
                    max = Math.max(max, maxEdge[a][j]);
                    a = up[a][j];
                }
            }

            if (a != b) {
                for (int j = levels - 1; j >= 0; j--) {
                    if (up[a][j] != up[b][j]) {
                        min = Math.min(min, Math.min(minEdge[a][j], minEdge[b][j]));
                        max = Math.max(max, Math.max(maxEdge[a][j], maxEdge[b][j]));
                        a = up[a][j];
                        b = up[b][j];
                    }
                }
                min = Math.min(min, Math.min(minEdge[a][0], minEdge[b][0]));
                max = Math.max(max, Math.max(maxEdge[a][0], maxEdge[b][0]));
            }
            output.append(min).append(' ').append(max).append('\n');
        }
        System.out.print(output);
    }
}