- Time limit: 1.00 s
- Memory limit: 512 MB
Annettuna on puu, jossa on n solmua. Tehtäväsi on laskea jokaiselle puun solmulle summa etäisyyksistä kaikkiin muihin solmuihin.
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 n kokonaislukua: jokaiselle solmulle 1,2,\dots,n summa etäisyyksistä kaikkiin muihin solmuihin.
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:
6 9 5 8 8