捞帖

树上回文串计数

树上每条边有一个小写字母，求有多少二元组 $(u,v)$ 使得路径上的字符依次拼接可以得到一个回文串。

二元组有序性任意。

$n\le10^5$

感觉这个问题和之前的帖子有所关联。

求助复杂度显著优于暴力的做法（不包括 $\dfrac{n^2}{w}$ 类）。