Codeforces Round #606 (Div. 1)

前言

可能当场上橙的场次，字符串防题根本看不到啊，虽然赛后也写了好久qwq。

题解

D - Tree Elimination

等价于求不同操作序列的个数，考虑树形。
令为以为根的子树在节点的删除情况为的方案数，为的父亲。共三种：

1. ，在遇到节点前被删除。
2. ，在遇到节点时被删除。
3. ，在遇到节点后被删除。

显然三个状态相互独立，考虑如何转移。
将的个儿子按照排序，其中，。

1. 如果在遇到之前被删除，那么必然在与某个儿子 相遇时被删除。
   依次考虑这样的，如果被删除,则必须在遇到之后被删除，则 需在遇到之前或者遇到时被删除， 则可以在遇到前被删除或遇到之后被删除但是不能在遇到时被删除。
   于是显然有。
2. 如果在遇到时被删除，则 需要在遇到之前或者遇到时被删除， 需要在可以在遇到之前或者遇到之后被删除但是不能在遇到时被删除。
   于是显然有
3. 如果在遇到之后被删除，假设在遇到时被删除，那么对于 ，必须在遇到之前被删除或者遇到时被删除，则 必须在遇到之前或遇到之后被删除，
   那么，后者为不删除的情况qwq。
   而叶子节点的初值为。