[BOJ] 1967번: 트리의 지름

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

D[i]를 i를 root로 하는 subtree에 속한 node 중에서 i로부터 가장 멀리 떨어진 것과의 거리라고 하면

D[i]는 i의 자식 c1, c2, ..., cn에 대해 max(D[c_j] + dist(i, c_j))입니다. D[i]는 재귀나 BFS로 구할 수 있습니다. D[i]를 구할 때 D[c_j] + dist(i, c_j)가 큰 2개의 j를 택해서 이 둘의 합과 현재 저장하고 있는 트리의 지름을 비교해(코드 상에서 mx) 큰 것으로 갱신해줍니다.

이 과정이 끝난 이후에 마지막으로 현재 저장하고 있는 트리의 지름과 D[1~N]을 비교해 큰 것으로 갱신하면 그것이 답이 됩니다. 이 과정이 없으면 모든 노드의 자식 노드가 1개 이하일 때 정상적인 답을 출력하지 못합니다.

https://github.com/encrypted-def/BOJ/blob/master/1967.cpp