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 $NN$ čvorova...

Ivan je iz sobe br. $119119$, promatrao to stablo, čvrsto ukorijenjeno u čvoru označenom brojem $11$. Nakon što je još pobliže promatrao stablo, primijetio je da se u svakom čvoru nalazi broj $a_{i}a\_i$. Odjednom mu je u glavu sinula definicija $kk$-dobrog podstabla. Neko podstablo je k-dobro, ako za svaki brid koji spaja čvorove $(u,v)(u,\; v)$ gdje je $uu$ roditelj od $vv$, vrijedi $a_v=(a_u+1)ka\_v\; =\; (a\_u\; +\; 1)\; \backslash bmod\; k$ te dodatno za svaki čvor $vv$ unutar podstabla vrijedi . Za svaki broj $kk$ postoji prirodna nestabilnost $kk$-dobrih stabala, označenu kao $f(k)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}k\_i$ tako da je ono $k_{i}k\_i$-dobro. Par biranja skupa bridova koje će prerezati te brojeva $k_{i}k\_i$ za svako tako dobiveno podstablo koji zadovoljavaju da je pripadajuće podstablo $k_{i}k\_i$-dobro, Ivan je odlučio nazvati rezanjem. Nestabilnost rezanja nazivamo zbroj $f(k_i)f(k\_i)$ po svim dobivenim podstablima. Pomozite Ivanu odrediti najmanju moguću nestabilnost rezanja!

입력

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

U drugom se retku nalazi $NN$ brojeva gdje $ii$-ti označava $a_{i}a\_i$ (0 ≤ a_i ≤ N - 1).

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

U sljedećih $N-1N\; -\; 1$ redaka nalazi se opis stabla, u $ii$-tom retku nalaze se brojevi $u_{i}u\_i$ te $v_{i}v\_i$ (1 ≤ u_i , v_i ≤ N, $u_i\mathrm{\ne }{v}_{i}u\_i\; \backslash ne\; v\_i$) koji označavaju da postoji brid među čvorovima $u_{i}u\_i$ te $v_{i}v\_i$.

출력

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

힌트