CF1771D Hossam and (sub-)palindromic tree

Hossam 有一棵无权树 $G$，树的每个顶点上都标有一个字母。 Hossam 定义 $s(v, u)$ 为从顶点 $v$ 到顶点 $u$ 的唯一简单路径上所有顶点的字母按顺序拼接得到的字符串。 如果字符串 $a$ 可以通过从字符串 $s$ 中删除若干（可以为零）个字母得到，则称 $a$ 是 $s$ 的一个子序列。例如，"dores"、"cf" 和 "for" 都是 "codeforces" 的子序列，而 "decor" 和 "fork" 不是。 回文串是指从左到右和从右到左读都相同的字符串。例如，"abacaba" 是回文串，而 "abac" 不是。 Hossam 定义字符串 $s$ 的子回文串为 $s$ 的一个子序列，且该子序列是回文串。例如，"k"、"abba" 和 "abhba" 都是字符串 "abhbka" 的子回文串，而 "abka" 和 "cat" 不是。 Hossam 定义字符串 $s$ 的极大子回文串为 $s$ 的所有子回文串中长度最大的那个。例如，"abhbka" 只有一个极大子回文串——"abhba"。但也可能存在多个极大子回文串，例如字符串 "abcd" 有 $4$ 个极大子回文串。 请你帮助 Hossam 求出树 $G$ 上所有 $s(v, u)$ 中极大子回文串的最大长度。 注意，子回文串是子序列，不是子串。

第一行包含一个整数 $t$（$1 \le t \le 200$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^3$），表示图中顶点的数量。 第二行包含一个长度为 $n$ 的字符串 $s$，第 $i$ 个字符表示顶点 $i$ 上的字母。保证该字符串中的所有字符均为小写英文字母。 接下来的 $n-1$ 行描述树的边。每条边由两个整数 $v$ 和 $u$（$1 \le v, u \le n$，$v \neq u$）组成，表示树中存在一条连接顶点 $v$ 和 $u$ 的边。保证给定的边构成一棵树。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^3$。

对于每个测试用例，输出一个整数，表示所有 $s(v, u)$ 中极大子回文串的最大长度。

在第一个样例中，极大子回文串为 "aaa"（顶点 $1, 3, 5$ 上的字母），或者 "aca"（顶点 $1, 4, 5$ 上的字母）。  第一组样例中的树。 在第二个样例中，只有一个极大回文串 "bacab"（顶点 $4, 2, 1, 5, 9$ 上的字母）。  第二组样例中的树。 由 ChatGPT 4.1 翻译