task16

[TOC]

1. THUPC2025 - I’m Here [E] ✔️

题面

给定一棵 $n$ 个点的有根树，保证 $1,2,\cdots,n$ 组成了一个合法的 dfs 序

第 $i$ 轮你可以进行如下操作：

• 选择一个还未被删除的点，将其子树中所有节点删除

第 $i$ 轮结束后，如果编号为 $n-i+1$ 的点还存在，那么它会被删除

对 $k=1,2,\cdots,n$，求 $k$ 轮之后将整棵树删空的方案数，对 $998244353$ 取模

$1\le n\le80$

题解

Sol

对于一个根，我们考虑其儿子的情况

设其 dfn 最大的子树大小为 $siz_1$，选了 $c_1$ 次操作，考虑这会对其它子树的操作产生什么影响

可以发现几乎没有什么影响，dfn 第二大的子树需要第 $i$ 个点在 $i$ 时刻及之前选，其中 $i\in[siz_1+1,siz_2]$，也就是说前面选的是哪 $c_1$ 次并不会改变选择数，我们一定是恰好有 $siz_1-c_1$ 的时间是可以选的

一般化一下，此时我们一棵子树的问题就是，前面有 $\sum siz-\sum c$ 的时间是可以随便选的，在这个时间之后，每一个时刻 dfn 最大的节点会被删除

但是我们还需要保证子节点的删除时刻小于父节点，因此我们需要再记一个变量，表示有多少时刻是可用的

最后我们的状态就是 $dp_{u,i,tl,tr}$，表示 $u$ 的子树内选了 $i$ 个点，现在这棵子树会从第 $tl+1$ 时刻开始每次删 dfn 最大的点，要求我们选的 $i$ 个点互不相同且时间戳均 $\le tr$（不要求时间戳连续）的方案数

转移先枚举 $tl,tr$，然后就是树形背包的复杂度，总复杂度 $O(n^4)$

---