P12238

· · 题解

看到前缀，考虑使用 trie，先把所有字符串扔到里面去。

然后发现要求方案数，于是考虑 dp，在本题中自然想到在 trie 上 dp 了。

具体而言，我们观察到 trie 有一种很好的性质：对于 trie 上的某个节点 u，u 的子树内所有叶子节点所对应的字符串都有根节点到 u 这条路径所对应的前缀。

这个性质有什么用呢？它意味着，我们只需选择某个节点，就可以将其子树内的所有字符串全部归于一类。

这样，问题转化为，在所有节点中选出 k 个不同节点并且每个子树必须选一个（为了满足条件 3）的方案数。这是个经典的树上背包问题，转移是显然的。

然后这题就做完了，实现有一些小细节会在代码中标注。