트리의 지름

Sol)

승자 트리를 생각하면 간단하다.
각 노드의 자식들 중 가장 큰 가중치의 줄기를 위로 올리면서 각 노드마다 자식들의 가중치 합 중 가장 큰 두가지를 골라 더한 후 max 값을 구하면 된다.

문제의 예제를 그림을 봐보자 편의상 1을 트리의 root로 보면 다음과 같은 트리가 나온다.

왼쪽의 트리를 구한 후 DFS방식으로 파고들어 우측 트리처럼 Leaf노드부터 차근차근 한층씩 올라가는 방식으로 해결하면 된다.