Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | arbsumpow.in, arbsumpow.out | Sursă | OSEPI Baraj Seniori 1 |
| Autor | Tamio-Vesa Nakajima | Adăugată de |  Matteo Verzotti •Matteoalexandru |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Arbsumpow
Municipiul B. a fost numit de curând staţiune turistică de interes naţional - astfel a decis să înceapă să desemneze anumite zone din oraş ca fiind centre culturale. Oraşul este format din N intersecţii, numerotate de la 1 la N, legate printre ele cu N - 1 drumuri, astfel încât oricare două intersecţii să fie legate direct sau indirect prin drumuri. Fiecare intersecţie are câte o valoare culturală, intersecţia i având valoarea v[i].
Oraşul poate desemna o mulţime S de intersecţii ca fiind centru cultural dacă şi numai dacă poţi ajunge din oricare intersecţie din S la oricare alta trecând doar prin intersecţii din S şi drumuri. Fie M mulţimea de mulţimi S ce pot fi desemnate ca centre culturale.
Pentru oricare mulţime de intersecţii S ∈ M, se consideră că valoarea culturală a centrului este dată de v(S), definit prin ![v(S) = \left( \sum_{x \in S} v[x]\right)^P,](http://www.infoarena.ro/static/images/latex/75554aa16daadf7203e9f2867eb45d6c_4.52977pt.gif "v(S) = \left( \sum_{x \in S} v[x]\right)^P,")
pentru o constantă P.
Municipiul va desemna fiecare mulţime din M ca fiind centru cultural pentru câte o zi, într-o ordine oarecare. Primăria este curioasă despre suma valorilor culturale a tuturor centrelor desemnate, modulo 109+7, adică 
Îi puteţi ajuta să găsească această valoare?
Date de intrare
În prima linie a fişierului de intrare arbsumpow.in se vor găsi valorile N, P. Urmează pe a doua linie valorile v[1], ..., v[N]. Pe cea de-a treia linie se vor găsi valorile p[2], ... , p[N], indicând că există pentru fiecare i de la 2 la N un drum între intersecţiile i şi p[i]. Se garantează ca p[i] < i oricare ar fi 1 < i ≤ N.
Date de ieşire
În fişierul de ieşire arbsumpow.out se va afişa o singură linie, ce conţine răspunsul cerut.
Restricţii
| Subtask | Punctaj | Restricţii |
|---|---|---|
| 1 | 7 | 1 ≤ N ≤ 15, 1 ≤ v[i] ≤ 109, 1 ≤ P ≤ 7 |
| 2 | 12 | 1 ≤ N ≤ 100, v[1] = ... = v[N] = 1, 1 ≤ P ≤ 7 |
| 3 | 5 | 1 ≤ N ≤ 1 000, v[1] = ... = v[N] = 1, 1 ≤ P ≤ 7 |
| 4 | 8 | 1 ≤ N ≤ 1 000, 1 ≤ v[i] ≤ 109, P = 1 |
| 5 | 10 | 1 ≤ N ≤ 100 000, 1 ≤ v[i] ≤ 109, P = 1 |
| 6 | 9 | 1 ≤ N ≤ 1 000, 1 ≤ v[i] ≤ 109, P = 2 |
| 7 | 13 | 1 ≤ N ≤ 100 000, 1 ≤ v[i] ≤ 109, P = 2 |
| 8 | 14 | 1 ≤ N ≤ 100 000, 1 ≤ v[i] ≤ 109, 1 ≤ P ≤ 7, o intersecţie e capătul a cel mult două drumuri |
| 9 | 22 | 1 ≤ N ≤ 100 000, 1 ≤ v[i] ≤ 109, 1 ≤ P ≤ 7 |
Exemple
| arbsumpow.in | arbsumpow.out |
|---|---|
| 3 2 1 2 3 1 1 | 75 |
| 4 1 9 10 9 10 1 2 1 | 190 |
| 5 2 1 2 3 4 5 1 1 3 3 | 1133 |
| 7 2 1 1 1 1 1 1 1 1 1 1 2 5 2 | 590 |
| 10 3 13 8 4 8 6 13 6 8 14 9 1 2 3 3 2 6 5 4 8 | 12312296 |
Explicaţie
Pentru primul exemplu, muchiile sunt (1, 2), (1, 3). Subarborii sunt determinaţi de următoarele mulţimi de noduri: {1}, {2}, {3}, {1, 2}, {1, 3}, {1, 2, 3}. Acestea au sumele 1, 2, 3, 3, 4, 6. Ridicând acestea la pătrat ne dă 1, 4, 9, 9, 16, 36, iar însumând ne dă 75.
