11. 트리

트리

Summary

트리는 사이클 없는 연결 그래프다.
부모 배열, 깊이, 서브트리 크기, 트리 지름이 자주 나온다.

---

트리 지름 검증 템플릿

Info

임의의 점에서 가장 먼 점 A를 찾고, A에서 가장 먼 거리로 지름을 구한다.

import java.io.*;
import java.util.*;
 
public class Main {
    static class Edge {
        int to;
        long cost;
 
        Edge(int to, long cost) {
            this.to = to;
            this.cost = cost;
        }
    }
 
    static List<Edge>[] tree;
    static boolean[] visited;
    static int farNode;
    static long farDist;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
 
        tree = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            tree[i] = new ArrayList<>();
        }
 
        for (int i = 0; i < n - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            long cost = Long.parseLong(st.nextToken());
            tree[a].add(new Edge(b, cost));
            tree[b].add(new Edge(a, cost));
        }
 
        visited = new boolean[n + 1];
        dfs(1, 0);
 
        visited = new boolean[n + 1];
        dfs(farNode, 0);
 
        System.out.println(farDist);
    }
 
    static void dfs(int node, long dist) {
        visited[node] = true;
 
        if (dist > farDist) {
            farDist = dist;
            farNode = node;
        }
 
        for (Edge next : tree[node]) {
            if (!visited[next.to]) {
                dfs(next.to, dist + next.cost);
            }
        }
    }
}

---

자주 쓰는 패턴

유형	처리
부모 찾기	DFS/BFS로 parent[next] = cur
깊이 계산	depth[next] = depth[cur] + 1
서브트리 크기	DFS 후 size[cur] += size[next]
트리 지름	DFS/BFS 2번
LCA 기초	부모/깊이 전처리

---

주의점

트리는 간선 수가 N - 1
무방향 입력이면 양쪽에 간선 추가
부모로 되돌아가지 않도록 visited 또는 parent 체크
재귀 깊이가 크면 StackOverflow 위험
가중치 합은 long 고려

---

백지 복원

1. 트리의 간선 수는?
2. 트리 지름을 DFS 2번으로 구하는 순서는?
3. 무방향 트리 입력에서 간선을 어떻게 저장하는가?