1 sekun\(da / 512\) M\(iB / 110\) points
You are given a sequence of \(n\) characters 0 or 1, indexed by numbers 1, 2, . . . , n. Initially every character
represents a string of length one. During a concatenation two words \(a\) and \(b\) are chosen, deleted, and
replaced by the string \(ab\) such that the characters of \(b\) are written after the characters of \(a\).
The \(n\) initial strings are concatenated to one final string using a sequence of \(n - 1\) concatenations. The \(i-th\)
of those concatenation is described by a pair of indexes (\(a@@RISE_MATH_BLOCK_0@@i-th\) character and the string containing \(b\)\(i-th\) character are to be concatenated. It is guaranteed that
characters with indexes \(a_{i}\) and \(b_{i}\) are not in the same string.
Palindromic value of some string \(w\) is defined as the total number of unique substrings of \(w\) which are
palindromes. We define palindromes as strings that are the same when read left to right and right to
left. A substring of a string is defined as a string obtained by erasing zero or more characters from the
beginning a\(nd/or\) ending of the string.
For every concatenation print the palindromic value of the resulting string.

Subtask 1 (10 points): \(1 \le n \le 100\).

Subtask 2 (20 points): \(1 \le n \le 1000\).

Subtask 3 (30 points): \(a@@RISE_MATH_BLOCK_0@@i = i + 1\) for all \(i = 1\), 2, . . . , \(n - 1\).

Subtask 4 (50 points): No additional constraints. 1 sekun\(da / 512\) M\(iB / 110\) points

The first line contains an integer \(n\) (\(1 \le n \le 100\,000\)), number of characters.
In the second line there is a string of \(n\) characters 0 and 1 which represent the initial strings.
The \(i-th\) of following \(n - 1\) lines contains two integers \(a@@RISE_MATH_BLOCK_0@@i\) (\(1 \le a@@RISE_MATH_BLOCK_1@@i\)̸ = \(b\)\(i\)) representing the \(i-th\)
concatenation.

Print \(n - 1\) lines, the palindromic values of words obtained after each concatenation.

생성자가 기록되지 않았습니다.

출처 COCI 2021/2022 Contest 6