ARC201C

Fearlessy · 2025-09-29 17:00:42 · 题解

小清新字典树。

首先有一个巧妙的转化。原问题实际上等价于，一棵满二叉树，你可以对某些点进行 01 染色，最终使得任意根到叶子的路径上至少有一个被染成 1 的节点。求合法染色方案数。

为什么是这样？把题目中的串扔到 trie 上。那么任意根到叶子的路径就是任意极长 AB 字符串。选择某个串 X 相当于在 trie 上 X 的结束位置染色。那么问题成功转化。

那么这个就是树上 dp 板子了。记 sz_i 表示 i 子树中可染色点的个数（包括自身），F_i 表示 i 子树的合法染色方案。同时记 ls_i，rs_i 表示 i 的左右儿子编号。

那么处理完 sz_i 后，对于 F_i 我们有：

• 若 i 可被染色，F_i = F_{ls_i} \times F_{rs_i} + 2^{sz_i-1}。
• 否则，F_i = F_{ls_i} \times F_{rs_i}。