Background

Translated from Izborne Pripreme 2023 (Croatian IOI/CEOI Team Selection) D2T3。$\texttt{1s,0.5G}$。

Happy birthday to NaCly_Fish! (2024.7.28).

Problem Description

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:

Input Format

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 Format

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

6 
8 6 2 4 2 6
1 2
3 4
5 7
6 8
9 10

36
4
0
12
4

7 
4 2 6 6 2 4 2
1 2
3 8
4 9
5 10
6 11
7 12

4
12
24
0
16
0 

8
4 10 2 10 6 8 4 12
1 2
3 4
5 6
7 8
9 10
11 12
13 14

16
4
36
16
84
28
0

Hint

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$.

Translated by ChatGPT 5