题解

思路

对一组树，令 $f(u,v)$ 表示路径 $u\rightsquigarrow v$ 的最长回文子序列长度。记 $x$ 为从 $u$ 走向 $v$ 的第一步，$y$ 为从 $v$ 走向 $u$ 的第一步。

做法

删除回文子序列左端未选的字符，可得到 $f(x,v)$；删除右端未选的字符，可得到 $f(u,y)$。若 $u,v$ 字符相同，还可以同时选择两个端点，得到 $2+f(x,y)$。因此

$$f(u,v)=\max\bigl(f(x,v),f(u,y),[s_u=s_v](2+f(x,y))\bigr).$$

按路径长度从短到长计算即可。长度为一个顶点时答案为 $1$；相邻端点相同时答案为 $2$，否则为 $1$。用每个点作为根遍历一次，可以预处理任意有序点对间的距离与第一步。所有 $f(u,v)$ 的最大值就是答案。

子任务一枚举每条路径的所有子序列。子任务二中每条路径本身都是回文串，答案等于树直径包含的顶点数。

复杂度

每组时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$；所有测试组的 $n$ 之和不超过 $2000$。