Codeforces Round #606 (Div. 1)
前言
可能当场上橙的场次,字符串防题根本看不到啊,虽然赛后也写了好久qwq。
题解
D - Tree Elimination
等价于求不同操作序列的个数,考虑树形。
令为以
为根的子树在节点
的删除情况为
的方案数,
为
的父亲。
共三种:
,
在遇到节点
前被删除。
,
在遇到节点
时被删除。
,
在遇到节点
后被删除。
显然三个状态相互独立,考虑如何转移。
将的
个儿子
按照
排序,其中
,
。
- 如果
在遇到
之前被删除,那么
必然在与某个儿子
相遇时被删除。
依次考虑这样的,如果
被
删除,则
必须在遇到
之后被删除,则
需在遇到
之前或者遇到
时被删除,
则可以在遇到
前被删除或遇到
之后被删除但是不能在遇到
时被删除。
于是显然有。
- 如果
在遇到
时被删除,则
需要在遇到
之前或者遇到
时被删除,
需要在可以在遇到
之前或者遇到
之后被删除但是不能在遇到
时被删除。
于是显然有 - 如果
在遇到
之后被删除,假设
在遇到
时被删除,那么对于
,
必须在遇到
之前被删除或者遇到
时被删除,则
必须在遇到
之前或遇到
之后被删除,
那么,后者为不删除的情况qwq。
而叶子节点的初值为
。