Problem Description

You are given a $\texttt{01}$ sequence of length $n$, indexed by $1,2,\dots,n$. Initially, each character represents a string of length $1$. In one concatenation operation, you need to choose two strings $a$ and $b$, delete them, and replace them with the string $ab$, i.e., write all characters of $a$ first and then write all characters of $b$.

These $n$ initial strings need to be merged into one string using $n-1$ concatenation operations. The pair of strings chosen in the $i$-th operation is described by an index pair $(a_i,b_i)$, meaning that the two strings to be concatenated are the one containing the character with index $a_i$ and the one containing the character with index $b_i$. It is guaranteed that the characters with indices $a_i$ and $b_i$ are not in the same string.

The palindrome value of some string $w$ is defined as the number of distinct palindromic substrings in $w$. We define a palindrome as a string that reads the same from left to right and from right to left. A substring of a string is defined as a string that can be obtained by deleting one or more characters from the beginning and/or the end of the string.

For each concatenation operation, output the palindrome value of the resulting string.

Input Format

The first line contains an integer $n$, representing the number of characters.

The second line contains a $\texttt{01}$ string of length $n$, representing the initial strings.

The next $n-1$ lines each contain two integers $a_i$, $b_i$, representing the $i$-th concatenation operation.

Output Format

Output $n-1$ lines, where the $i$-th line is the palindrome value of the string obtained after the $i$-th concatenation operation.

3
010
1 2
2 3

2
3

5
00111
4 1
1 5
2 1
3 1

2
3
4
5

8
10010000
7 5
4 2
3 6
1 3
6 8
5 3
1 2

2
2
2
3
4
6
8

Hint

Sample Explanation 3:

After each concatenation, the newly created strings are: $\tt 00, 10,00, 100, 1000,001000$ and $\tt 00100010$.

Their palindrome values are given in the sample output. For example, the palindrome value of $\tt 00100010$ is $8$, because the string contains $8$ palindromic substrings: $\tt 0, 00, 000, 10001,0100010, 1010$ and $00100$.

Constraints:

For $9\%$ of the testdata: $1\le n\le100$.

For $18\%$ of the testdata: $1\le n\le1000$.

For $27\%$ of the testdata: $a_i = 1, b_i = i + 1$.

For $100\%$ of the testdata: $1\le n\le10^5$, $1\le a_i, b_i\le n$.

The scoring for this problem is the same as COCI 2021-2022#6, with a full score of $110$ points.

Translated by ChatGPT 5