P8406 [COCI 2021/2022 #6] Palindromi

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.

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 $n-1$ lines, where the $i$-th line is the palindrome value of the string obtained after the $i$-th concatenation operation.

### 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](https://hsin.hr/coci/contest6_tasks.pdf), with a full score of $110$ points. Translated by ChatGPT 5