BOJ. Diameter of Tree (1167)

Problem

In a tree with nonnegative edge weights, start from any vertex and find a farthest vertex a; then find a farthest vertex from a. The distance found in the second traversal is the tree diameter. A farthest vertex from an arbitrary start is a diameter endpoint: if a diameter path is considered alongside the paths from the start, the tree’s unique paths and nonnegative weights imply that one of the diameter endpoints is at least as far from the start, and extending from that farthest vertex reaches a diameter endpoint. This is the standard two-sweep property for weighted trees.

The input gives every vertex’s adjacency list, so each undirected edge already appears once from each endpoint. Add only the listed directed adjacency entries; inserting a reverse entry as well would duplicate edges. Each list ends with the vertex number -1, which must be recognized before attempting to read an edge weight. Both traversals use an explicit stack, avoiding recursion depth limits on a long chain. A long distance safely accumulates the path lengths. One vertex has no edges, so both sweeps simply return that vertex with diameter zero.

The two traversals and graph construction take O(V) time for V vertices (E = V - 1), and the adjacency lists, stack, and visited/distance arrays use O(V) space.

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

public class Main {
    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner();
        int vertexCount = input.nextInt();
        List<Edge>[] graph = new List[vertexCount];
        for (int i = 0; i < vertexCount; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < vertexCount; i++) {
            int vertex = input.nextInt() - 1;
            while (true) {
                int neighbor = input.nextInt();
                if (neighbor == -1) break;
                long weight = input.nextInt();
                graph[vertex].add(new Edge(neighbor - 1, weight));
            }
        }

        int endpoint = farthestVertex(graph, 0).vertex;
        long diameter = farthestVertex(graph, endpoint).distance;
        System.out.println(diameter);
    }

    private static Result farthestVertex(List<Edge>[] graph, int start) {
        int[] stack = new int[graph.length];
        boolean[] visited = new boolean[graph.length];
        long[] distance = new long[graph.length];
        int size = 0;
        stack[size++] = start;
        visited[start] = true;
        int farthest = start;

        while (size > 0) {
            int vertex = stack[--size];
            if (distance[vertex] > distance[farthest]) {
                farthest = vertex;
            }
            for (Edge edge : graph[vertex]) {
                if (visited[edge.to]) continue;
                visited[edge.to] = true;
                distance[edge.to] = distance[vertex] + edge.weight;
                stack[size++] = edge.to;
            }
        }
        return new Result(farthest, distance[farthest]);
    }

    private static final class Edge {
        final int to;
        final long weight;

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

    private static final class Result {
        final int vertex;
        final long distance;

        Result(int vertex, long distance) {
            this.vertex = vertex;
            this.distance = distance;
        }
    }

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

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

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

            int sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }
            int value = 0;
            while (c > ' ') {
                value = value * 10 + c - '0';
                c = read();
            }
            return value * sign;
        }
    }
}