Ehtiyat kabel — Eolymp

Giriş

Birinci sətirdə bir tam $n$ ədədi ( $3 \leq n \leq 2 \cdot 1 0^{5}$ 3\le n\le 2\cdot10^5) — şəhərlərin sayı verilir.

Növbəti $n - 1$ n-1 sətrin hər birində iki tam $u_{i}, v_{i}$ u_i,v_i ədədi ( $1 \leq u_{i}, v_{i} \leq n$ 1\le u_i,v_i\le n, $u_{i} \neq = v_{i}$ u_i\ne v_i) — $i$ -ci ilkin yolun ucları verilir.

İlkin yol şəbəkəsinin ağac olduğu zəmanət verilir.

Çıxış

Bir tam ədəd — bir yeni yol tikildikdən sonra zərərlərin mümkün olan minimal cəmini çap edin.

Nümunələr

Nümunə 1

Loading

Nümunə 2

Loading

Nümunə 3

Loading

Qeyd

Birinci nümunədə $1$ və $4$ şəhərləri arasında yol tikmək olar. Bundan sonra istənilən ilkin yoldakı qəza şəbəkənin əlaqəliliyini pozmur. Buna görə cavab $0$ -dır.

İkinci nümunədə $2$ və $3$ şəhərləri arasında yol tikmək olar. $(1, 2)$ və $(1, 3)$ yollarındakı qəzalar şəbəkənin əlaqəliliyini pozmur, $(1, 4)$ yolundakı qəza isə bir şəhəri təcrid edir. Zərərlərin cəmi $1$ olur.

Üçüncü nümunədə yeni yol yalnız iki ilkin yolu qoruya bilər. Digər iki qəzanın hər biri bir şəhəri təcrid edir. Buna görə cavab $2$ -dir.

Bal hesablama

Altməsələ $1$ ( $20$ bal): $n \leq 9$ n\le 9.
Altməsələ $2$ ( $40$ bal): $n \leq 100$ n\le 100.
Altməsələ $3$ ( $60$ bal): $n \leq 2000$ n\le 2000.
Altməsələ $4$ ( $80$ bal): ən çox bir şəhər ilkin yollarla ikidən çox digər şəhərə birbaşa birləşdirilib.
Altməsələ $5$ ( $100$ bal): əlavə məhdudiyyət yoxdur.