Det er $N$ byer i JOI-riket, som er nummerert med tallene fra $1$ til $N$. By $1$ er hovedstaden. Hver by har en verdi som kalles livlighet, og startverdien for livligheten til by $i$ ($1 \le i \le N$) er $C_i$.
En vei i JOI-riket forbinder to forskjellige byer i begge retninger. Til å begynne med er det ingen veier i JOI-riket. Du har planlagt $N-1$ veibygginger. Den $j$-te byggingen ($1 \le j \le N-1$) er planlagt utført på følgende måte.
- To byer, $A_j$ og $B_j$, blir utpekt, der man kan reise fra by $1$ til by $A_j$ og ikke kan reise fra by $1$ til by $B_j$ ved kun å bruke veier som er bygget på det tidspunktet.
Du bygger en vei som forbinder by $A_j$ og by $B_j$. Kostnaden for denne byggingen er antallet par av byer $(s,t)$ som tilfredsstiller følgende betingelser:
By $s$ og by $t$ ligger på den korteste veien mellom by $1$ og by $A_j$, og når man reiser fra by $1$ til by $A_j$ ankommer man by $s$ før by $t$, og livlighetsverdien til by $s$ er strengt større enn den til by $t$.
Her inkluderer byene som ligger på veien mellom by $1$ og by $A_j$ også by $1$ og by $A_j$. Merk at den korteste veien mellom by $1$ og by $A_j$ er unik.
Livlighetsverdiene til alle byer som ligger på veien mellom by $1$ og by $A_j$ endres til livlighetsverdien til by $B_j$.
Du ønsker å vite kostnaden for hver bygging.
Oppgave
Gitt data om byene og veibyggingene, skriv et program som beregner kostnaden for hver bygging.
Inndata
Les følgende data fra standard inndata.
- Den første linjen i inndataene inneholder et heltall $N$. Dette betyr at det er $N$ byer i JOI-riket.
- Den andre linjen i inndataene inneholder $N$ heltall $C_1, C_2, \cdots C_N$ adskilt med mellomrom. Dette betyr at startverdien for livligheten til by $i$ ($1 \le i \le N$) er $C_i$.
- Den $j$-te linjen ($1 \le j \le N-1$) av de følgende $N-1$ linjene inneholder to heltall $A_j$, $B_j$ adskilt med mellomrom. Dette betyr at by $A_j$ og by $B_j$ er utpekt for den $j$-te veibyggingen.
Utdata
Skriv $N-1$ linjer til standard utdata. Den $j$-te linjen ($1 \le j \le N-1$) i utdataene skal inneholde kostnaden for den $j$-te veibyggingen.
Begrensninger
Alle inndata tilfredsstiller følgende betingelser.
- $1 \le N \le 100\,000$.
- $1 \le C_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
- $1 \le A_j \le N$ ($1 \le j \le N-1$).
- $1 \le B_j \le N$ ($1 \le j \le N-1$).
- Ved å bruke veier bygget før den $j$-te byggingen kan man reise fra by $1$ til by $A_j$ og kan ikke reise fra by $1$ til by $B_j$ ($1 \le j \le N-1$).
Deloppgaver
Det er 3 deloppgaver. Poengsummen og tilleggsbegrensningene for hver deloppgave er som følger:
Deloppgave 1 [7 poeng]
- $N \le 500$.
Deloppgave 2 [9 poeng]
- $N \le 4000$.
Deloppgave 3 [84 poeng]
Det er ingen ytterligere begrensninger.
Eksempler
Inndata 1
5 1 2 3 4 5 1 2 2 3 2 4 3 5
Utdata 1
0 0 0 2
Forklaring
I eksempelinndata 1 utføres byggingene som følger:
- I den første byggingen er det ingen par $(s,t)$ som tilfredsstiller betingelsene, så kostnaden er $0$. En vei som forbinder by $1$ og by $2$ blir bygget, og livlighetsverdien til by $1$ endres til $2$.
- I den andre byggingen er det heller ingen par $(s,t)$ som tilfredsstiller betingelsene, så kostnaden er $0$. En vei som forbinder by $2$ og by $3$ blir bygget, og livlighetsverdiene til by $1$ og by $2$ endres til $3$.
- I den tredje byggingen er det heller ingen par $(s,t)$ som tilfredsstiller betingelsene, så kostnaden er $0$. En vei som forbinder by $2$ og by $4$ blir bygget, og livlighetsverdiene til by $1$ og by $2$ endres til $4$.
- I den fjerde byggingen tilfredsstiller to par $(s,t)=(1,3),(2,3)$ betingelsene, så kostnaden er $2$. En vei som forbinder by $3$ og by $5$ blir bygget, og livlighetsverdiene til by $1$, by $2$ og by $3$ endres til $5$.
Inndata 2
10 1 7 3 4 8 6 2 9 10 5 1 2 1 3 2 4 3 5 2 6 3 7 4 8 5 9 6 10
Utdata 2
0 0 0 1 1 0 1 2 3