不知道为啥有断更了一周...
woc,怎么跟我出的题目这么像
先把字符串扔到一个 Trie 里面,然后对于每一个点我们考虑这一个点到根节点组成的字符串能是多少对字符串的最长公共前缀。
我们定义 \(cnt_u\) 表示共有多少个字符串的结尾在以 \(u\) 为根的子树内。对于 \(u\) 节点,其贡献即为 \(dep \times \sum_{v \in son_u,w \in son_u} cnt_u \times cnt_w\)。然后把每一个点的贡献加起来即可。
标签:cnt,一个点,times,ABC353,字符串,son From: https://www.cnblogs.com/Carousel/p/18187274