== 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$ ...

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$
** Cel mult un nod are mai mult de $1$ muchie incidentă.

h2. Restricţii

* *Subtask 5 (30 puncte)*
** $N ≤ 300000$
** Oricare nod are cel mult 3 muchii incidente.

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

* *Subtask 6 (20 puncte)*
** $N ≤ 300000$

h2. Exemplu
table(example). |_. arbset.in |_. arbset.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4
2 1 3 4
1 2
1 3
1 4
| 11

|
h3. Explicaţie

...

Mulţimile bune sunt ∅ (cu mărimea $0$), ${1}, {2}, {3}, {4}$ (cu mărimea $1$), ${1, 3}, {1, 4}$ (cu mărimea $2$) şi ${1, 3, 4}$ (cu mărimea $3$). Astfel rezultatul este $11$.

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