Fişierul intrare/ieşire:	arbset.in, arbset.out	Sursă	Science on 2021, baraj
Autor	Tamio-Vesa Nakajima	Adăugată de	Nicola Alexandra Mihaela •Nicolaalexandra
Timp execuţie pe test	1 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Arbset

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?

Date de intrare

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.

Date de ieşire

Fişierul de ieşire arbset.out conţine răspunsul cerut, modulo 10⁹ + 7.

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ă.

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

• Subtask 6 (20 puncte)
  • N ≤ 300000

Exemplu

arbset.in	arbset.out
4 2 1 3 4 1 2 1 3 1 4	11

Explicaţie

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

Cum se trimit solutii?