- Time limit: 1.00 s
- Memory limit: 512 MB
Annettuna on puu, jossa on n solmua. Tehtäväsi on etsiä mahdollisimman suuri paritus eli joukko kaaria, jossa jokainen solmu on enintään yhden kaaren päätesolmuna.
Syöte
Ensimmäisellä rivillä on kokonaisluku n: solmujen määrä. Solmut on numeroitu 1,2,\dots,n.
Sitten syötteessä on n-1 riviä, jotka kuvaavat kaaret. Jokaisella rivillä on kaksi kokonaislukua a ja b: solmujen a ja b välissä on kaari.
Tuloste
Tulosta yksi kokonaisluku: suurin parituksen koko.
Rajat
- 1 \le n \le 5 \cdot 10^5
- 1 \le a,b \le n
Esimerkki
Syöte:
5 1 2 1 3 3 4 3 5
Tuloste:
2
Selitys: Yksi mahdollinen ratkaisu on (1,2) ja (3,4).