28385번 - Nestabilnost 서브태스크다국어

Borova šuma na suprotnoj obali rijeke, još prije jednog sata osvijetljena svibanjskim suncem, zamutila se, razmazala i rasplinula. Ostalo je samo jedno divovsko stablo, stablo s $N$ čvorova...

Ivan je iz sobe br. $119$, promatrao to stablo, čvrsto ukorijenjeno u čvoru označenom brojem $1$. Nakon što je još pobliže promatrao stablo, primijetio je da se u svakom čvoru nalazi broj $a_i$. Odjednom mu je u glavu sinula definicija $k$-dobrog podstabla. Neko podstablo je k-dobro, ako za svaki brid koji spaja čvorove $(u, v)$ gdje je $u$ roditelj od $v$, vrijedi $a_v = (a_u + 1) \bmod k$ te dodatno za svaki čvor $v$ unutar podstabla vrijedi $a_v < k$. Za svaki broj $k$ postoji prirodna nestabilnost $k$-dobrih stabala, označenu kao $f(k)$.

Kada se ponovno osvrnuo, primijetio je da pluta pred stablom s magičnom pilom u desnoj ruci. Ivan je odlučio prerezati neke grane, te za svako podstablo, dobiveno micanjem prepiljenih bridova, odabrati neki broj $k_i$ tako da je ono $k_i$-dobro. Par biranja skupa bridova koje će prerezati te brojeva $k_i$ za svako tako dobiveno podstablo koji zadovoljavaju da je pripadajuće podstablo $k_i$-dobro, Ivan je odlučio nazvati rezanjem. Nestabilnost rezanja nazivamo zbroj $f(k_i)$ po svim dobivenim podstablima. Pomozite Ivanu odrediti najmanju moguću nestabilnost rezanja!

U prvom je retku prirodan broj $N$, broj čvorova stabla.

U drugom se retku nalazi $N$ brojeva gdje $i$-ti označava $a_i$ ($0 ≤ a_i ≤ N - 1$).

U trećem se retku nalazi $N$ brojeva gdje $k$-ti označava $f(k)$ ($1 ≤ f(k) ≤ 10^9$).

U sljedećih $N - 1$ redaka nalazi se opis stabla, u $i$-tom retku nalaze se brojevi $u_i$ te $v_i$ ($1 ≤ u_i , v_i ≤ N$, $u_i \ne v_i$) koji označavaju da postoji brid među čvorovima $u_i$ te $v_i$.

U jedini redak potrebno je ispisati najmanju moguću nestabilnost rezanja.