Codeforces Round #606 (Div. 1)

前言

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

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

显然三个状态相互独立，考虑如何转移。
将 $u$ 的 $n$ 个儿子 $v$ 按照 $idx[u,v]$ 排序，其中 $idx[u,v1...v_k]<idx[u,p]$ ， $idx[u,v_{k+1}...v_n]>idx[u,p]$ 。

如果 $u$ 在遇到 $p$ 之前被删除，那么 $u$ 必然在与某个儿子 $v_i$ $i\in[1,k]$ 相遇时被删除。
依次考虑这样的 $v_1,v_2,v_3...v_k$ ，如果 $u$ 被 $v_i$ 删除,则 $v_i$ 必须在遇到 $u$ 之后被删除，则 $v_j$ $j\in[1,i-1]$ 需在遇到 $u$ 之前或者遇到 $u$ 时被删除， $v_j$ $j\in[i+1,n]$ 则可以在遇到 $u$ 前被删除或遇到 $u$ 之后被删除但是不能在遇到 $u$ 时被删除。
于是显然有 $dp[u][0]=\sum_{i=1}^{k}(\prod_{j=1}^{i-1}(dp[v_j][0]+dp[v_j][1])*dp[v_i][2]*\prod_{j=i+1}^{n}(dp[v_j][0]+dp[v_j][2]))$ 。
如果 $u$ 在遇到 $p$ 时被删除，则 $v_i$ $i\in[1,k]$ 需要在遇到 $u$ 之前或者遇到 $u$ 时被删除， $v_i$ $i\in[k+1,n]$ 需要在可以在遇到 $u$ 之前或者遇到 $u$ 之后被删除但是不能在遇到 $u$ 时被删除。
于是显然有 $dp[u][1]=\prod_{i=1}^{k}(dp[i][0]+dp[i][1])\prod_{i=k+1}^{n}(dp[i][0]+dp[i][2])$
如果 $u$ 在遇到 $p$ 之后被删除，假设 $u$ 在遇到 $v_i$ 时被删除，那么对于 $v_i$ $i\in[1,i-1]$ ， $v_i$ 必须在遇到 $u$ 之前被删除或者遇到 $u$ 时被删除，则 $v_i$ $i\in[i+1,k]$ 必须在遇到 $u$ 之前或遇到 $u$ 之后被删除， $v_i$
那么 $dp[u][2]=\sum_{i=k+1}^{n}(\prod_{j=1}^{i-1}(dp[v_j][0]+dp[v_j][1])*dp[v_i][2]*\prod_{j=i+1}^{n} (dp[v_j][0]+dp[v_j][2]))+\prod_{i=1}^{n}(dp[v_i][0]+dp[v_i][1])$ ，后者为不删除的情况qwq。
而叶子节点 $u$ 的初值为 $dp[u][0]=0,dp[u][1]=1,dp[u][2]=1$ 。