== include(page="template/taskheader" task_id="arbset") ==

Poveste şi cerinţă...

Mioara are un arbore cu $N$ noduri, unde rădăcina este nodul $1$, şi unde fiecare nod $i$ are câte o valoare $v[i]$ între $1$ şi $N$. Toate valorile sunt distincte. O submulţime $A$ de noduri se numeşte bună dacă şi numai dacă:
 
1. Oricare două noduri $i, j ∈ A$, unde $i$ este strămoşal lui $j$, satisfac $v[i] < v[j]$;
2. Pentru oricare două noduri $i, j ∈ A$, dacă $l$ este cel mai adânc strămos, comun al lui $i$ şi $j$, atunci $l ∈ A$.
 
Mioara este curioasă: care este suma valorilor $|A|$ (adică mărimea lui $A$) pentru toate mulţimile $A$ bune?
 

h2. Date de intrare

Fişierul de intrare $arbset.in$ ...

Fişierul de intrare $arbset.in$ conţine pe primul rând numărul $N$. Pe a doua linie se află valorile $v[ 1 ]$, . . . , $v[ N ]$. Urmează $N − 1$ rânduri, fiecare conţinând două valori $x$, $y$, ce indică existenţa unei muchii de la $x$ la $y$.

h2. Date de ieşire

În fişierul de ieşire $arbset.out$ ...

În fişierul de ieşire $arbset.out$ conţine răspunsul cerut, modulo 10^9^ + 7.
 
h2. Subtaskuri
 
* *Subtask 1 (10 puncte)*
** $N ≤ 20$
 
* *Subtask 2 (20 puncte)*
** $N ≤ 2000$
 
* *Subtask 3 (10 puncte)*
** $N ≤ 300000$
** Oricare nod are cel mult $2$ muchii incidente.
 
* *Subtask 4 (10 puncte)*
*** $N ≤ 300000$
** OCel mult un nod are mai mult de 1 muchie incident

h2. Restricţii

*Subtask 5 (30 puncte)*
** $C = 2, N ≤ 8$

* $... ≤ ... ≤ ...$

* *Subtask 6 (20 puncte)*
** $C = 2, N ≤ 18$

h2. Exemplu