BOJ 24545 - Y

BOJ 24545 - Y

트리 DP를 관리하며 rerooting으로 풀 수 있다.

그냥 어떤 트리가 가지는 가장 길게 뻗어나가는 길이를 multiset으로 관리하면 편하다.

다른 풀이는 트리의 지름을 이용하는 풀이이다.

$Y$ 에서 가장 긴 선 하나는 트리의 지름이라는 점을 이용하여 트리의 지름에 있는 모든 정점들에 대해서 트리의 지름 줄기를 제외한 간선들로 최대로 뻗어나가는 길이의 최대값을 찾는 풀이도 가능하다.