백준 1167 트리의 지름

https://www.acmicpc.net/problem/1167

 

 이 문제는 트리에서 가장 먼 두 정점 사이의 거리를 구하는 문제이다. 

 

 트리에서 가장 긴 지름은 무조건 말단 노드와 말단 노드 사이일 것이다. 그리고 임의의 노드에서 가장 먼 노드가 그 지름의 말단 노드일 것이다. 자세한 증명은 https://blog.myungwoo.kr/112 이 블로그를 참고하길 바란다.

 

 아무튼 결국 우리는 임의의 노드(루트노드)에서 가장 먼 노드를 구하고, 그 노드에서 가장 먼 노드를 구하면 된다.

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def find(cur_n,cur_w):
    for next_w,next_n in tree[cur_n]:
        if visited[next_n] == -1:
            visited[next_n] = cur_w+next_w
            find(next_n,visited[next_n])

N=int(input().rstrip())
tree = [[] for _ in range(N+1)]

for _ in range(N-1):
    a = list(map(int,input().rstrip().split()))
    p=a[0]
    for idx in range(1,len(a)-1,2):
        c,w=a[idx],a[idx+1]
        tree[p].append([w,c])
        tree[c].append([w,p])


visited=[-1 for _ in range(N+1)]
visited[1]=0
find(1,0)

start = visited.index(max(visited))
visited=[-1 for _ in range(N+1)]
visited[start]=0
find(start,0)

print(max(visited))