h2. Date de intrare

Fişierul de intrare $dedicatie.in$ contine pe prima linie numarul natural $N$, cu semnificatia din enunt. Pe urmatoarele $N-1$ linii se afla cate doua numere naturale $x$ si $y$ cu semnificatia ca exista o muchie intre aceste doua noduri. Pe ultima linie a fisierului de intrare se afla cele $N-1$ elemente ale vectorului $alfa$ separate prin cate un spatiu (vectorul este indexat de la $0$).

Fişierul de intrare $dedicatie.in$ contine pe prima linie numarul natural $N$, cu semnificatia din enunt. Pe urmatoarele $N-1$ linii se afla cate doua numere naturale $x$ si $y$ cu semnificatia ca exista o muchie intre aceste doua noduri. Pe ultima linie a fisierului de intrare se afla cele $N-1$ elemente ale vectorului $alfa$ separate prin cate un spatiu (vectorul este indexat de la 0).

h2. Date de ieşire

$muchia 5 (1 -> 5): 1$
Dupa inmultirea cu $alfa$, muchiile au valorile finale:

$muchia 1 (5 -> 4): (0 * 7574) $%$ 100003 = 0$
$muchia 2 (4 -> 2): (2 * 1) $%$ 100003 = 2$
$muchia 3 (3 -> 1): (3 * 66670) $%$ 100003 = 4$
$muchia 4 (4 -> 6): (4 * 25002) $%$ 100003 = 5$
$muchia 5 (1 -> 5): (1 * 2) $%$ 100003 = 2$

$muchia 1 (5 -> 4): (0 * 7574)$ % $100003 = 0$
$muchia 2 (4 -> 2): (2 * 1) % 100003 = 2$
$muchia 3 (3 -> 1): (3 * 66670) % 100003 = 4$
$muchia 4 (4 -> 6): (4 * 25002) % 100003 = 5$
$muchia 5 (1 -> 5): (1 * 2) % 100003 = 2$

Permutarea optima este: $4 5 2 1 6 3$
<tex> \sum_{i=1}^{6} dist(i, p(i)) = 2 + 2 + 4 + 2 + 2 + 4 = 16</tex> si este maxima