[CF2183F] Jumping Man 题解

只能说我对树形 DP 的理解还是太狭隘了，甚至没想过可以两维都表示点。

设 表示 子树内的点（不含 ）。求平方是难受的，考虑经典 trick，转化为求有多少对串串相同。设 表示 以 开头的串串 和 以 开头的串串 匹配的方案数，显然它当且仅当 时有值，且有 。因为涉及到子树，所以这个转移在 dfs 序上就是一个矩形的形式，做一下二维后缀和即可，详见代码。时间复杂度 。

Submission。