Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Rataverkko

Rataverkko


View task | Model solution | Statistics


Rataverkko

Time limit:1.00 s
Memory limit:128 MB

Bittimaan rataverkko muodostuu $n$ asemasta ja $n-1$ rataosuudesta niiden välillä. Miltä tahansa asemalta pääsee mille tahansa asemalle. Tehtäväsi on käsitellä joukko kyselyjä, joissa tehtävänä on laskea etäisyys kahden aseman välillä.

Syöte

Syötteen alussa on kaksi kokonaislukua $n$ ja $q$: asemien määrä ja kyselyiden määrä. Asemat on numeroitu $1,2,\ldots,n$.

Sitten syötteessä on $n-1$ riviä, jotka kuvavat rataosuudet. Jokaisella rivillä on kolme kokonaislukua $a$, $b$ ja $c$: asemien $a$ ja $b$ välissä on rataosuus, jonka pituus on $c$. Kaikki rataosuudet ovat kaksisuuntaisia.

Lopuksi syötteessä on $q$ riviä, jotka kuvaavat kyselyt. Jokaisella rivillä on kaksi kokonaislukua $a$ ja $b$: tehtävänä on laskea etäisyys asemien $a$ ja $b$ välillä.

Tuloste

Tulosta vastaus jokaiseen kyselyyn.

Rajat
Esimerkki

Syöte:
5 3
1 2 5
2 3 2
2 4 4
4 5 3
2 4
3 5
1 4


Tuloste:
4
9
9