Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | arbquery.in, arbquery.out | Sursă | Science On 2021, clasele 11-12 |
| Autor | Tamio-Vesa Nakajima | Adăugată de |  Sandulescu Alexandru •alexsandulescu |
| Timp execuţie pe test | 1.5 sec | Limită de memorie | 268435 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Arbquery
Manuela are un arbore cu N noduri, unde fiecare muchie are câte o lungime. Un lanţ este o secvenţă de noduri distincte x_1, ..., x_k, astfel încât să existe câte o muchie între oricare două noduri adiacente. Numim lungimea unui lanţ x_1, ..., x_k suma lungimilor muchiilor care unesc nodurile adiacente din drum. Pentru fiecare muchie (x, y) fie d(x, y) suma lungimilor tuturor lanţurilor care conţin muchia de la x la y.
Manuela are Q interogări, fiecare de forma unui lanţ x_1, ..., x_k. Ea vrea să afle suma d(x_1, x_2) + ... + d(x_{k-1}, x_k) % 109 + 7.
Date de intrare
Primul rând al fişierului de intrare arbquery.out conţine numărele N şi Q. Urmează N - 1 rânduri, fiecare conţinând trei valori x, y, l, ce indică existenţa unei muchii de la x la y cu lungimea l. Urmează apoi Q linii, fiecare conţinând două valori x, y, ce reprezintă o interogare asupra lanţului unic de la x la y.
Date de ieşire
Fişierul de ieşire arbquery.out conţine răspunsurile celor Q interogări, în ordine.
Subtaskuri
- Subtask 1 (10 puncte)
- N, Q ≤ 20.
- Oricare muchie are lungimea cel mult 105.
- Subtask 2 (30 puncte)
- N, Q ≤ 2.000.
- Oricare muchie are lungimea cel mult 105.
- Subtask 3 (10 puncte)
- N, Q ≤ 100.000.
- Oricare nod are cel mult 2 muchii incidente.
- Oricare muchie are lungimea cel mult 105.
- Subtask 4 (10 puncte)
- N, Q ≤ 100.000.
- Cel mult un nod are mai mult de 1 muchie incidentă.
- Oricare muchie are lungimea cel mult 105.
- Subtask 5 (40 puncte)
- N, Q ≤ 100.000.
- Oricare muchie are lungimea cel mult 105.
Exemplu
| arbquery.in | arbquery.out |
|---|---|
| 3 3 1 2 1 2 3 100 1 2 2 3 1 3 | 102 201 303 |
Observăm că sunt trei lanţuri, 1 - 2 de cost 1, 2 - 3 de cost 100 şi 1 - 2 - 3 de cost 101. Astfel d(1, 2) = 102, d(2, 3) = 201. Astfel rezultatul pentru 1, 2 este d(1, 2) = 102, pentru 2, 3 este d(2, 3) = 201, şi pentru 1, 3 este d(1, 2) + d(2, 3) = 303.
