第 4 题 Palindromi (palindromi)

CSP-S 复赛模拟赛 21 · 时间限制 1.0 s · 空间限制 256 MB · 47 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 palindromi.in，输出文件 palindromi.out。

题目描述

给你一个长度为 $n$ 的 01 序列，下标为 $1, 2, \ldots, n$。最初每个字符都代表了一个长度为 1 的字符串。在一次连接中，需要选择两个字符串 $a$ 和 $b$，将它们删除后，换为字符串 $ab$，即在写下 $a$ 中的所有字符后写下字符串 $b$ 的所有字符。

这 $n$ 个初始字符串需要用 $n - 1$ 次连接操作连成一个字符串。第 $i$ 次选择的字符串用一个下标对 $(a_i, b_i)$ 描述，表示要连接的字符串是包含下标为 $a_i$ 的字符的和包含下标为 $b_i$ 的字符的。保证下标为 $a_i$ 和 $b_i$ 的字符不在同一字符串中。

一些字符串 $w$ 的回文值被定义为 $w$ 中不同回文子串的个数。我们定义回文串为从左到右读和从右到左读相同的字符串。一个字符串的子串被定义为可以从字符串开头和（或）结尾开始删去一个或多个字符得到的字符串。

对于每次连接操作，输出每次连成的字符串的回文值。

输入格式

第一行包含一个整数 $n$，表示字符个数。

第二行一个长度为 $n$ 的 01 字符串，表示初始字符串。

接下来 $n - 1$ 行，每行两个整数 $a_i$，$b_i$，表示第 $i$ 次连接操作。

输出格式

输出 $n - 1$ 行，表示每次连接操作得到的字符串的回文值。

样例

样例 1

输入：

3
010
1 2
2 3

输出：

2
3

样例 2

输入：

5
00111
4 1
1 5
2 1
3 1

输出：

2
3
4
5

样例 3

输入：

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

输出：

2
2
2
3
4
6
8

提示

样例解释 3：

在每个连接之后新创建的字符串是： 00，10，00，100，1000，001000 和 00100010。

它们各自的回文值在样例输出中给出。例如 00100010 的回文值是 8，因为字符串包含8回文子字符串：0，00，000，10001，0100010，1，010 和 00100。

数据范围：

对于 9% 的数据：$1 \le n \le 100$

对于 18% 的数据：$1 \le n \le 1000$

对于 27% 的数据：$a_i = 1, b_i = i + 1$

对于 100% 的数据：$1 \le n \le 10^5$，$1 \le a_i, b_i \le n$

本题分值与 COCI 2021-2022#6 分值相同，满分 110 分