Gym103119B

Semsue · 2023-07-02 17:17:26 · 题解

https://codeforces.com/gym/103119/problem/B

此题 acam 上主元法明显会比 pgf 好做。我以前此类题目全都背结论，硬币游戏勉强能做，但此题好似就无从下手。

因为无论硬币游戏还是歌唱王国都是在串与串之间考虑，此题如果这么搞会有 |R| 个串。

比较暴力的方法是 acam 上每个节点都设一个位置数，然后记 acam 上转移时 trans_{u,c}，有 f_{u}=\sum\limits_{c}f_{trans_{u,c}}p_c+1。

注意到叶子个数总和是 O(n) 的，而分叉个数也是 O(n) 的。考虑用这些当主元列方程。

把每个 trie 树上的节点取 deg-1 个儿子当未知数，剩下一个可以用其他表示。注意到 acam 的转移只会跑到 dep 更小的节点上去。使用 bfs 即可。