COCI '21 Contest 6 #4 Palindromi

View as PDF

Submit solution


Points: 25 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types

You are given a sequence of n characters, 0 or 1, indexed by numbers 1, 2, \dots, 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^\text{th} of those concatenation is described by a pair of indices (a_i, b_i), which denotes that the string containing a_i^\text{th} character and the string containing b_i^\text{th} character are to be concatenated. It is guaranteed that characters with indices 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.

Input Specification

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^\text{th} of following n-1 lines contains two integers a_i, b_i (1 \le a_i, b_i \le n, a_i \ne b_i) representing the i^\text{th} concatenation.

Output Specification

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

Constraints

Subtask Points Constraints
1 10 1 \le n \le 100
2 20 1 \le n \le 1\,000
3 30 a_i = 1, b_i = i+1 for all i = 1, 2, \dots, n-1.
4 50 No additional constraints.

Sample Input 1

3
010
1 2
2 3

Sample Output 1

2
3

Sample Input 2

5
00111
4 1
1 5
2 1
3 1

Sample Output 2

2
3
4
5

Sample Input 3

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

Sample Output 3

2
2
2
3
4
6
8

Explanation for Sample Output 3

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 substrings: 0, 00, 000, 10001, 0100010, 1, 010, 00100.


Comments

There are no comments at the moment.