31977번 - Minequake 서브태스크다국어

문제

The fully autonomous microbreweries installed in the abandoned Dwarven mines of Moravia are truly a testament to the ingenuinity and craftsmanship of Dwarven engineering! Alas, sometimes earthquakes rattle the mines, leading to misaligned pipes and funnels spilling precious liquid on the floor. As the Exalted Warden of Brewery Safety it is your responsibility to turn off the machines in every hall in case of an earthquake.

Walking through tunnels takes time, so you will inevitably arrive late at many of the machines. This cannot be avoided, but you want to minimise the total amount of spilled liquid.

The Dwarven mines consist of $n$ halls connected by $n-1$ tunnels. The entire system is connected, so it is possible to get from any hall to any of the others. It takes 1ドル$ unit of time to traverse a tunnel. Switching off a machines and traversing a hall takes no time. In each hall, turning off the machines at time $t$ after the earthquake spills $t$ liters of liquid. There is exactly one earthquake, the earthquake affects all halls at the same time, and you may not switch off any machines before the earthquake. You can start in any of the halls.

In sample input 1ドル,ドル the mines look like this:

If you start in hall 2ドル$ and visit the rest of the halls in the order 2ドル,ドル 1ドル,ドル 2ドル,ドル 3ドル,ドル then you can switch off their machines at time 0ドル$ (in hall 2ドル$), time 1ドル$ (in hall 1ドル$), and time 3ドル$ (in hall 3ドル$). This wastes 0ドル+1+3=4$ liters of liquid in total. If instead you start in hall 1ドル$ and visit the halls in the order 1ドル,ドル 2ドル,ドル 3ドル,ドル the total amount of liquid wasted is 0ドル+1+2=3$ liters, which is better.

입력

The first line of input consists of the integer $n,ドル denoting the number of halls. We assume that the halls are numbered 1ドル,ドル $\ldots,ドル $n$. The next $n-1$ lines each contain two space-separated integers $u$ and $v$ with 1ドル\leq u < v \leq n,ドル meaning that there is a tunnel between hall $u$ and hall $v$.

출력

Print a single integer: the minimum amount of spilled liquid, in liters.

제한

We always have 1ドル\leq n\leq 10^5$.

서브태스크

힌트