Fişierul intrare/ieşire:hacker2.in, hacker2.outSursăONI 2011 - Baraj
AutorAndrei ParvuAdăugată desavimSerban Andrei Stan savim
Timp execuţie pe test0.25 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Hacker2

Proaspăt ieşit de pe băncile facultăţii, Bujorel s-a decis că cea mai bună meserie pe care o poate urma este cea de hacker. Astfel, el a dat peste o reţea de N calculatoare, etichetate de la 1 la N, dispuse sub forma unui graf ponderat care este arbore. Fiecare muchie are o pondere, care reprezintă distanţa dintre cele două calculatoare aflate în nodurile muchiei. Distanţa dintre oricare două calculatoare se defineşte ca suma distanţelor de pe lanţul dintre ele.
Înainte de a îşi începe atacul, Bujorel va avea M cerinţe. O cerinţă este de forma unei perechi (x, p), unde x reprezintă indicele unui calculator din arbore, iar p o distanţă. El vrea să determine poziţia de pe o muchie unde poate fi amplasat un nou calculator astfel încât distanţa dintre noul calculator şi calculatorul cu indicele x să fie exact p.

Cerinţă

Pentru a deveni ucenicul lui Bujorel, tu trebuie să răspunzi corect la cele M cerinţe.

Date de intrare

Fişierul de intrare hacker2.in conţine pe prima linie N şi M, numărul de calculatoare din reţea, respectiv numărul de întrebări. Următoarele N–1 linii conţin triplete de forma (x, y, d) reprezentând o legătură directă între calculatorul x şi calculatorul y de distanţă d. Ultimele M linii conţin perechi de forma (x, p) reprezentând cerinţa: “Găsiţi două calculatoare a şi b din arbore între care există o muchie, şi o poziţie k pe muchie, astfel încât suma dintre k şi distanţa de la x la a să fie exact p ”.

Date de ieşire

Fişierul de ieşire hacker2.out va conţine M linii reprezentând răspunsurile la cele M cerinţe. Un răspuns va fi de forma (a, b, k) însemnând că pe muchia dintre calculatoarele a şi b se va amplasa un nou calculator aflat la distanţa k faţă de a.

Restricţii

  • 1 ≤ N, M ≤ 100 000
  • 1 ≤ x, y ≤ N
  • 1 ≤ d ≤ 64
  • Pentru un răspuns de forma (a, b, k), k trebuie să fie în intervalul [0, D(a, b)], unde D(a, b) este distanţa de la calculatorul a la calculatorul b.
  • Toate numerele din fişierele de intrare, respectiv de ieşire vor fi numere naturale.
  • Se garantează faptul că pentru fiecare întrebare există un răspuns.
  • Orice soluţie corectă este acceptată.

Exemplu

hacker2.inhacker2.out
8 4
1 2 1
1 7 1
7 8 1
2 3 1
2 4 1
4 5 1
4 6 1
4 3
2 1
2 3
1 3
7 1 0
1 7 0
8 7 0
6 4 0
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content