Fişierul intrare/ieşire:arbquery.in, arbquery.outSursăScience On 2021, clasele 11-12
AutorTamio-Vesa NakajimaAdăugată dealexsandulescuSandulescu Alexandru •alexsandulescu
Timp execuţie pe test1.5 secLimită de memorie268435 kbytes
Scorul tăuN/ADificultateN/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.inarbquery.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?