P10834 [COTS 2023] Problem Zadatak

Translated from [Izborne Pripreme 2023 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2023/) D2T3。$\texttt{1s,0.5G}$。 Happy birthday to NaCly_Fish! (2024.7.28).

Jura has $N$ squares, numbered $1\sim N$. The side length of the $i$-th square is $a_i$, and $2\mid a_i$. Initially, all these squares are black. Jura decides to spend $(N-1)$ seconds of his life playing with these squares. In the $i$-th second, Jura merges the $x_i$-th and the $y_i$-th squares into the $(N+i)$-th square (after the merge, the $x_i$-th and $y_i$-th squares no longer exist). When merging squares, align the centers of the two squares, and place them on the plane with their edges parallel. The new square has the side length of the larger one among the two squares being merged. Its color is the “xor sum” of the original colors (black + black = white, white + white = white, black + white = black, white + black = black). The **cost** of a merge is the area of the region that is black in both squares within their intersection before merging (but after placing them as required above). You need to output the cost of each merge operation. The figure below shows an example of merging squares: 

The first line contains a positive integer $N$, denoting the number of squares. The second line contains $N$ positive integers describing the array $a$. The next $(N-1)$ lines each contain two positive integers $x_i,y_i$, describing one operation.

Output $(N-1)$ lines, each containing one integer, denoting the cost of the operation.

### Sample Explanation The last operation of sample $1$ is shown in the figure below:  #### Constraints For $100\%$ of the testdata, it is guaranteed that: - $1\le N\le 10^5$. - $2\le a_i\le 10^6$. - $2\mid a_i$. - $1\le x_i,y_i\le N+i-1$. - Before each operation, the squares exist, and $x_i\neq y_i$. | Subtask ID | Points | Constraints | |:-----:|:------:|:-------:| | $1$ | $14$ | $N\le 5\, 000$ | | $2$ | $25$ | $x_1=1,y_1=2$；$\forall 2\le i\le N-1$，$x_i=i+1,y_i=N+i-1$ | | $3$ | $17$ | $\exists k\in \mathbb{N}$，such that $2^k=N$；$x_i=2i-1,y_i=2i$ | | $4$ | $21$ | $n\le 30\, 000$ | | $5$ | $23$ | No additional constraints | Translated by ChatGPT 5