| Fişierul intrare/ieşire: | hacker2.in, hacker2.out | Sursă | ONI 2011 - Baraj |
| Autor | Andrei Parvu | Adăugată de |  Serban Andrei Stan •savim |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | hacker2.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 |
