- Time limit: 1.00 s
- Memory limit: 512 MB
Annettuna on puu, jossa on n solmua. Tehtäväsi on laskea puun läpimitta eli kuinka pitkä on pisin puussa oleva polku.
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: puun läpimitta.
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:
3
Selitys: Läpimittaa vastaa esimerkiksi polku 2 \rightarrow 1 \rightarrow 3 \rightarrow 5.