CF2183F Jumping Man 笔记

经典 Trick：平方考虑转换为其组合意义。

在本题中，$c^2(s)$ 可以看成有 $c(s)$ 个路径可以组成 $s$，从中无限制选择两个的方案数。

因此可以 DP：设 $f_{i,j}$ 表示考虑分别从 $i,j$ 两点出发，能够走出相同字符串的方案数，转移直接在继承子树里某点的答案，如下：

$$f_{i,j}\leftarrow [s_i=s_j](1+\sum _{u\in \mathrm{son}(i)\wedge v\in \mathrm{son}(j)}{f}_{u,v})$$

状态数 $O(n^2)$，转移 $O(n^2)$，显然可以优化子树的转移，把 ${\mathrm{dfn}}_i$ 拍到 $x$ 轴，${\mathrm{dfn}}_j$ 拍到 $y$ 轴就是一个矩形求和的形式，由于深度从大到小 DP 因此直接从后往前做不需要 $\log$ 数据结构，时空复杂度 $O(n^2)。$

最终答案为 $\sum _{u\in \mathrm{son}(1)\wedge v\in \mathrm{son}(1)}{f}_{u,v}$，同理求和。