문제

입력
12
1 2 3
1 3 2
2 4 5
3 5 11
3 6 9
4 7 1
4 8 7
5 9 15
5 10 4
6 11 6
6 12 10
-> 45

point

• 거리 계산은 DFS이용

모든 node에서 최대 거리를 구하면 안된다.

• 모든 leaf간 거리 중 최대

  • 트리의 지름을 구성하는 node는 leaf node이다.
  • leaf ( : 간선이 하나인 node ) 배열을 구하고,
    모든 leaf간 (combination) 거리 중 최대인 것을 출력했다.
  • 시간 초과 발생

• non-leaf node간 거리 DP로 관리

  • leaf node의 부모 node간 거리는 매번 leaf node간 거리를 계산 할 때 마다 반복 계산된다.
  • DP로 최하위 non-leaf node 간 거리를 관리 했다.
  • 메모리 초과 발생

트리의 지름의 rule

• 모든 node간 경로는 하나 뿐이다.
• 어떤 node에서 가장 거리가 먼 node는 트리의 지름을 구성하는 node 중 하나다.