Lemon Tree timer 1s memory 1024MB

♬ I wonder how, I wonder why. ♬

-Fool's Garden의 <Lemon Tree> 중

노란 레몬 나무가 한 그루 보인다.

레몬 나무는 정점이 N개이며 1번 정점이 루트인 트리이다.

(트리란 사이클이 없는 연결 그래프를 의미한다.)

처음에는 나무에 레몬이 한 개도 열려있지 않아 노랗지 않다.

이 트리의 정점에 한 개씩 레몬이 열리기 시작하면서 나무가 점점 노랗게 보이는 것이다.

한 정점에는 최대 한 개의 레몬이 열리고 따라서 최대 N개의 레몬이 열릴 수 있다.

어떤 레몬 나무의 노란 정도는 다음과 같은 정점 쌍 (u, v)의 개수와 같다.

• u와 v 모두에 레몬이 열려 있다.

• u는 v의 조상 정점이다.

레몬이 k개 열려 있는 레몬 나무 중 가장 덜 노란 나무의 노란 정도를 0에서 N까지의 모든 k에 대해 구해보자.