트리의 지름

트리에서 가장 긴 길이의 경로를 뜻한다. 이심률이라고도 하는 듯하다.

방법은 아래와 같다.

1. 임의의 정점(A)을 선택한다.
2. 임의의 정점에서 가장 긴 정점(B)을 찾는다.
3. B 정점에서 가장 긴 정점(C) 를 찾는다.
4. B - C 의 경로가 가장 긴 경로이다.

이를 통해 다시 느낄 수 있는 트리는 순환이 없다 그래서 간선의 수는 정점의 수 N - 1 이다.

위의 경우 각 거리의 비용(가중치)이 1이라는 가정하에 길이를 다뤘지만
문제에 따라 정점마다 점수를 줄 수도 있다. 이 경우엔 길이가 아닌 점수로 똑같이 적용하면 된다.

모든 점수가 양수라면 문제는 더 쉽다. 다익스트라처럼

import java.util.*;
import java.io.*;

public class 나무_위의_벌거지_2132 {
    public static List<Integer> lllog = new ArrayList<>();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] tree = new int[n];
        String[] inputs = br.readLine().split(" ");
        List<ArrayList<Integer>> path = new ArrayList<>(); // 반공변 한 번 더 체크
        for (int i = 0; i < n; i++) {
            tree[i] = Integer.parseInt(inputs[i]);
            path.add(new ArrayList<>());
        }
        
        for (int i = 0; i < n - 1; i++) {
            inputs = br.readLine().split(" ");
            int n1 = Integer.parseInt(inputs[0]) - 1;
            int n2 = Integer.parseInt(inputs[1]) - 1;
            path.get(n1).add(n2);
            path.get(n2).add(n1);
        }

        // 0 최대 합, 1 최대 노드
        int[] res = {-1, 10005};
        boolean[] visited = new boolean[n];
        visited[0] = true;
        dfs(res, tree, path, visited, 0, tree[0]);
        visited[0] = false;
        
        int start = res[1];
        res[0] = -1;
        res[1] = 10005;
        visited[start] = true;
        dfs(res, tree, path, visited, start, tree[start]);
        visited[start] = false;

        int last = res[1];
        int max = res[0];
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write("" + max + " " + (Math.min(start, last) + 1));
        bw.flush();
    }
    
    public static void dfs(int[] res, int[] tree, List<ArrayList<Integer>> path, boolean[] visited, int cur, int curSum) {
        if (res[0] < curSum || res[0] == curSum && cur < res[1]) {
            res[0] = curSum;
            res[1] = cur;
        }
        for (int next : path.get(cur)) {
            if (visited[next]) continue;
            visited[next] = true;
            dfs(res, tree, path, visited, next, curSum + tree[next]);
            visited[next] = false;
        }
    }
}