정올이는 크리스마스를 기념해 N개의 정점으로 이루어진 크리스마스 트리를 청소하려 한다.

정올이는 두개의 리프 정점을 지정해, 두 리프 정점을 지나는 경로를 따라 수건으로 먼지를 털어내는 것을 반복할 것이다. 이 과정에서 걸리는 시간은 경로 상의 간선의 개수와 같다. 하지만 리프 정점은 연약하기에, 리프 정점은 정확히 1번씩만 지정할 것이다.

모든 간선을 최소 한번씩 수건으로 청소하기 위한 최소 시간을 구해보자.

단순히 이를 해결하는 것은 너무 지루했던 정올이는, 크리스마스 트리의 모양을 조금 바꾼 형태에서 위 물음을 해결하고자 한다. 구체적으로, V번 정점에 1개의 간선을 추가해 1개의 새로운 리프를 생성할 것이다. 이 과정에서 기존에 리프였던 정점이 리프가 아니게 될 수도 있음에 주의하자.

각각의 변화된 트리에서 정올이의 물음을 해결하자. 변화는 누적되지 않는다는 것에 주의하자.

#6131 upload 12 done 3 how_to_reg 3

크리스마스 트리 timer 1s memory 1024MB

#6131

크리스마스 트리 1s 1024MB