레이팅 미적용1 sekunda / 512 MiB / 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_{i}\), \(b_{i}\)), which denotes that the string containing
\(a_{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 and/or ending of the string.
For every concatenation print the palindromic value of the resulting string.
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_{i}\) i \(b_{i}\) (\(1 \le a_{i}\), \(b_{i} \le n\), \(a_{i}\)̸ = \(b_{i}\)) representing the \(i\)-th
concatenation.
Print \(n - 1\) lines, the palindromic values of words obtained after each concatenation.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 10점 | \(1 \le n \le 100\). |
2 | 20점 | \(1 \le n \le 1000\). |
3 | 30점 | \(a@@RISE_MATH_BLOCK_0@@i = i + 1\) for all \(i = 1\), 2, . . . , \(n - 1\). |
4 | 50점 | No additional constraints. 1 sekun\(da / 512\) M\(iB / 110\) points |
3
010
1 2
2 32
35
00111
4 1
1 5
2 1
3 12
3
4
58
10010000
7 5
4 2
3 6
1 3
6 8
5 3
1 22
2
2
3
4
6
8Clarification of the third example:
Newly created strings after every concatenation are: 00, 10, 00, 100, 1000, 001000 and 00100010. Their
respective palindromic values are given in the example output. E. g. the palindromic value of 00100010
is 8 because the string contains 8 palindromic substring: 0, 00, 000, 10001, 0100010, 1, 010 i 00100.