paths_sums

Time limit: 0.5s Memory limit: 64MB Input: Output:

Cerință

Se dau un arbore cu NN noduri cu rădăcina în nodul 11 al cărui muchii au lungimi exprimate prin numere naturale nenule și QQ query-uri de forma u vu \ v. Pentru fiecare query să se afle suma lungimilor tuturor drumurilor distincte de la un nod aflat în subarborele cu rădăcina în nodul uu la un nod aflat în subarborele cu rădăcina în nodul vv modulo 109+710^9 + 7. (lungimea unui drum este egală cu suma lungimilor tuturor muchiilor ce îl alcătuiesc).

Date de intrare

Pe prima linie se vor citi de la tastatură numerele NN și QQ reprezentând numărul de noduri din arbore, respectiv numărul de query-uri.

Următoarele N1N - 1 linii conțin câte 2 numere pi wip_i \ w_i, i=2,Ni=\overline{2,N}, reprezentând tatăl nodului ii în arbore, respectiv lungimea muchiei dintre pip_i și ii (nodul 11 este rădăcina arborelui, deci nu are tată).

Pe următoarele QQ linii se va afla câte un query.

Date de ieșire

Programul va afișa pe ecran pe câte o linie rezultatele query-urilor, în ordinea în care acestea apar în input.

Restricții și precizări

  • 1N200 0001 \leq N \leq 200 \ 000
  • 1Q500 0001 \leq Q \leq 500 \ 000
  • 1wi1 000 000 0001 \leq w_i \leq 1 \ 000 \ 000 \ 000
  • 1u,vN1 \leq u, v \leq N
  • pentru fiecare query de tipul 22, subarborii cu rădăcinile în nodurile uu, respectiv vv nu vor avea noduri comune.

Exemplu

stdin

14 4
1 4
1 3
2 2
2 7
2 10
3 12
3 5
4 8
4 1
5 3
7 6
7 4
8 9
4 8
2 7
9 11
12 8

stdout

129
595
20
55

Explicație

Arborele descris în exemplu arată în felul următor:

Pentru primul query drumurile sunt:

  • De la 44 la 88 de lungime 1414
  • De la 44 la 1414 de lungime 2323
  • De la 99 la 88 de lungime 2222
  • De la 99 la 1414 de lungime 3131
  • De la 1010 la 88 de lungime 1515
  • De la 1010 la 1414 de lungime 2424

Total: 14+23+22+31+15+24=12914 + 23 + 22 + 31 + 15 + 24 = 129

Log in or sign up to be able to send submissions!