Problem D
Kaevandusvärin

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

Moraavia mahajäetud pöialpoiste kaevandustesse paigaldatud täisautomaatsed mikropruulikojad on märk pöialpoissinseneride suurepärastest võimetest ja geniaalsusest! Mõnikord aga raputavd kaevandusi maavärinad, mistõttu lähevad torud ja lehtrid nihkesse ning väärtuslik vedelik voolab maha. Pruulikojaturvalisuse Pühaliku Kaitsjana on sinu ülesanne maavärina korral igas ruumis olev masin välja lülitada.

Tunnelite läbimine võtab aega, seega jõuad sa kindlasti paljude masinate juurde liiga hilja. Seda vältida ei ole võimalik, küll aga soovid sa minimeerida mahaläinud vedeliku mahtu.

Pöialpoisikaevandused koosnevad $n$ ruumist, mis on omavahel ühendatud $n-1$ tunneliga. Terve süsteem on sidus, seega on igast ruumist võimalik jõuda igasse teise ruumi. Tunneli läbimine võtab $1$ ühiku aega. Masina välja lülitamine ja ruumi läbimine aega ei võta. Mistahes ruumis oleva masina välja lülitamine $t$ ajaühikut pärast maavärinat ajab maha $t$ liitrit vedelikku. Toimub täpselt üks maavärin, see maavärin mõjutab kõiki ruume samaaegselt ning sa ei saa enne maavärinat ühtki masinat välja lülitada. Sa võid alustada mistahes ruumist.

Näide

Näites $1$ näevad kaevandused välja nii:

Kui alustada ruumis $2$ ja külastada ruume järjekorras $2$, $1$, $2$, $3$, siis saab masinad välja lülitada aegadel $0$ (ruumis $2$), $1$ (ruumis $1$) ja $3$ (ruumis $3$). Nii läheb kokku raisku $0+1+3=4$ liitrit vedelikku. Kui aga alustada ruumis $1$ ja külastada ruume järjekorras $1$, $2$, $3$, siis läheb raisku $0+1+2=3$ liitrit, mis on eelmisest parem tulemus.

Sisend

Sisendi esimesel real on täisarv $n$, ruumide arv. Eeldame, et ruumid on nummerdatud $1$, $\ldots $, $n$. Järgmised $n-1$ rida koosnevad igaüks kahest tühikutega eraldatud täisarvust $u$ ja $v$, kus $1\leq u < v \leq n$, mis tähendab, et ruumide $u$ ja $v$ vahel on tunnel.

Väljund

Trüki välja üksainus täisarv: vähim võimalik mahaläinud vedeliku kogus liitrites.

Piirangud ja hindamine

Alati kehtib $1\leq n\leq 10^5$.

Selles ülesandes on testid jagatud gruppidesse, iga grupp on väärt mingi arvu punkte. Iga grupi eest saavad punkte vaid need lahendused, mis läbivad kõik sellesse gruppi kuuluvad testid. Sinu lõplik skoor on esituste maksimum.

3
1 2
2 3

3

4
1 2
1 3
1 4

7

1

0