Problem D
Mineskælv

Goodluck Mine, Passage af Ashley Dace. Licens CC BY-SA 2.0.

De helautonome mikrobryggerier, der er blevet bygget i Moravias forladte dværgminer, bærer i sandhed vidnesbyrd om dværgfolkets opfindsomhed og håndværkskunst! Desværre rystes minerne sommetider af jordskælv, der fører til at de deraf forskudte rør og tragte spilder kostbar væske på gulvet. Som den ophøjede vogter for bryggerisikkerhed er det dit ansvar at slukke maskinerne i hver hal i tilfælde af et jordskælv.

Det tager tid at gå gennem tunnelerne, så du vil uundgåeligt komme for sent til mange af maskinerne. Dette kan ikke undgås, men du ønsker at minimere den samlede mængde af spildt væske.

Dværgminerne består af $n$ haller forbundet af $n-1$ tunneler. Hele systemet er forbundet, så det er muligt at komme fra hver hal til hver af de andre. Det tager $1$ tidsenhed at passere en tunnel. At slukke for en maskine og passere en hal tager ingen tid. I hver hal gælder, at hvis maskinerne slukkes ved tidspunkt $t$ efter jordskælvet, så spildes $t$ liter væske. Der er præcis ét jordskælv, jordskælvet påvirker alle haller samtidigt, og du må ikke slukke for nogen maskiner inden jordskælvet. Du kan starte i hvilken hal, du vil.

Eksempel

I eksempel $1$ ser minerne sådan her ud:

Hvis du begynder i hal $2$ og besøger resten af hallene i rækkefølgen $2$, $1$, $2$, $3$, kan du slukke deres maskiner ved tidspunkt $0$ (i hal $2$), tidspunkt $1$ (i hal $1$) og tidspunkt $3$ (i hal $3$). Dette spilder sammenlagt $0+1+3=4$ liter væske. Hvis du derimod starter i hal $1$ og besøger hallerne i rækkefølgen $1$, $2$, $3$, så er den samlede mængde af spildt væske $0+1+2=3$ liter, hvilket er bedre.

Indlæsning

Første linje af indlæsningen består af heltallet $n$, som angiver antallet af haller. Vi antager, at hallerne er nummereret $1$, $\dots$, $n$.

Hver af de næste $n-1$ linjer består af to heltal $u$ og $v$, adskilte af mellemrum, som opfylder $1\le u<v\le n$ og betyder, at der er en tunnel mellem hal $u$ og hal $v$.

Udskrift

Skriv et enkelt heltal: det mindste antal liter spildt væske.

Begrænsninger og pointsætning

Der gælder altid $1\le n\le {10}^5$.

Din løsning vil blive testet på en række testgrupper, hver med en vist antal point. Hver testgruppe indeholder en række testfald. For at opnå point for en testgruppe skal du løse alle testfald i testgruppen. Din endelige score vil være den højeste score for en enkelt indsendelse.

3
1 2
2 3

3

4
1 2
1 3
1 4

7

1

0