|
English versionFirstly, consider a classical dp to calculate $dp_{u,k}$ as the number of delete $k$ vertices in subtree $u$ without considering deleting vertex $n-i+1$ everyday. This is trivial. Then, due to the existence of an “automatic deletion” process, we cannot view the selected points within the subtree of $u$ as operations with only relative order, because they may be illegal. However, we consider the final operation sequence, putting the vertex chosen on the $i$ th day in the position $n-i+1$. That is, if we firstly choose $4$, then $3$, then $1$, it will be $0431$. Then, one vertex $u$ must be put in position $u$ or later. Then, we find that for the subtree of vertex $u$ with DFS order interval $[l,r]$, all vertex can't be put in position before $l$, and always legal to put in position after $r$ if parent-child relations are satisfied. So we consider a dp $f_{u,i,j,k}$ which represents that the subtree of $u$ leaves position $i$ for ancestors (which means nothing can be placed at position $i$ or before, and if $i=0$, then nothing is left for ancestors), there are $j$ empty spaces (not including the one left for ancestors), and $k$ vertices need to be put into positions after the subtree of $u$. In the $i=0$ case,we merge subtrees,and the subtree with smaller DFS order can put some backward operations into the space of the subtree with bigger DFS order. Specifically, consider the sons of $u$ enumerated in reverse order of DFS, and the son is $v$.Then enumerate $w$ as how many backward operations from $v$ will fill in space of $u$. The transition is $f_{u,0,j+j1-w,k+k1-w} \leftarrow f_{u,0,j+j1-w,k+k1-w}+f_{u,0,j,k}\times f_{v,0,j1,k1}\times {j \choose w}\times{k+k1-w \choose k}$. For $f_{v,i,j,k}(i\neq 0)$, it won't interfere the transition with its following siblings. And for $f_{u,i,j,k}$, just consider where to put $u$. The answer for $i$ operations is $f_{1,i,i-2,0}$. 中文版本对于树上选一个点删去一个子树方案数这个经典问题，一个常见的 dp 是记 $dp_{u,k}$ 为 $u$ 子树选 $k$ 个点方案数，转移时兄弟间用组合数将其合并，然后祖先要选就必须选在它们前面，这一部分 $O(n^2)$。 回到本题，由于存在“自动删点”的过程因此我们不能将 $u$ 子树内选的点看成只有相对顺序的操作，因为其可能不合法。但我们考虑最终的操作序列，没有的位置留空：比如样例 $1$ 中第一次选 $4$，第二次选 $3$，第三次选 $1$，那么操作序列即为 $0 4 3 1$。也就是第 $i$ 次选的点放在 $n-i+1$ 的位置上。这样，我们发现一个点 $u$ 只能填在 $u$ 及以后的位置，那么对于一个点 $u$ 的子树，其 dfs 序区间为 $[l,r]$，那么 $u$ 子树的点填到 $r$ 以后的位置一定合法，而 $u$ 留的空其前面的兄弟和祖先填进去只要没有父子关系干扰一定合法，于是我们考虑 dp。 考虑一个 dp $f_{u,i,j,k}$ 表示 $u$ 子树 $i$ 这个位置留给祖先（也就是说 $i$ 及以前不能放东西，如果 $i=0$ 就不留），有 $j$ 个空（不包含给祖先留的），有 $k$ 个点要填到 $u$ 子树以后的位置。先考虑 $i=0$ 情况。那么合并两个子树的时候就是 dfs 序更小的子树可以选一些向后的操作填到 dfs 序更大子树的空里面。然后两个子树的空合并，向后操作合并。 具体来说，考虑 $u$ 的儿子按 dfs 序倒序枚举，对于一个儿子 $v$，那么合并 $f_{u,0,j,k}$ 和 $f_{v,0,j1,k1}$ 的时候先枚举一个 $w$ 代表选多少个 $v$ 中的向后操作填到 $u$ 的 $v$ 之后的子树，转移即为 $f_{u,0,j+j1-w,k+k1-w}\leftarrow f_{u,0,j+j1-w,k+k1-w}+f_{u,0,j,k}\times f_{v,0,j1,k1}\times {j \choose w}\times{k+k1-w \choose k}$。 再考虑 $f_{v,i,j1,k1}$ ，发现它需要给祖先留空并不影响其和后面兄弟的转移，因此转移同上，只是 $v$ 留的空 $u$ 同样需要留，所以转移到 $f_{u,i,j+j1-w,k+k1-w}$。注意这里需要预处理转移系数（因为 $i$ 取任何值转移系数相同）才能达到 $O(n^5)$。 然后考虑 $f_{u,i,j,k}$ 的转移，即 $v$ 后面的子树已经留了空。那么 $v$ 子树现在不能放任何东西，但是可以用一些向后的操作填 $i$ 后面的空，这里用 $dp_{v,k}$ 去转移即可。 子树转移完后，接下来是 $u$ 自身的操作。$u$ 可以有几种选择：
最后求答案的时候，对于要求 $k$ 次操作，相当于给 $1$ 在 $n-k+1$ 的位置留了空，同时恰好只有 $n-k$ 个空（那么后面就没有空，就是合法的操作序列），输出即可。
题目4286 [THUPC 2025 Final] I’m Here
AAAAAAAAAAAAA
评论
2026-01-29 18:40:31
|
|
|
English versionFirstly, consider a classical dp to calculate $dp_{u,k}$ as the number of delete $k$ vertices in subtree $u$ without considering deleting vertex $n-i+1$ everyday. This is trivial. Then, due to the existence of an “automatic deletion” process, we cannot view the selected points within the subtree of $u$ as operations with only relative order, because they may be illegal. However, we consider the final operation sequence, putting the vertex chosen on the $i$ th day in the position $n-i+1$. That is, if we firstly choose $4$, then $3$, then $1$, it will be $0431$. Then, one vertex $u$ must be put in position $u$ or later. Then, we find that for the subtree of vertex $u$ with DFS order interval $[l,r]$, all vertex can't be put in position before $l$, and always legal to put in position after $r$ if parent-child relations are satisfied. So we consider a dp $f_{u,i,j,k}$ which represents that the subtree of $u$ leaves position $i$ for ancestors (which means nothing can be placed at position $i$ or before, and if $i=0$, then nothing is left for ancestors), there are $j$ empty spaces (not including the one left for ancestors), and $k$ vertices need to be put into positions after the subtree of $u$. In the $i=0$ case,we merge subtrees,and the subtree with smaller DFS order can put some backward operations into the space of the subtree with bigger DFS order. Specifically, consider the sons of $u$ enumerated in reverse order of DFS, and the son is $v$.Then enumerate $w$ as how many backward operations from $v$ will fill in space of $u$. The transition is $f_{u,0,j+j1-w,k+k1-w} \leftarrow f_{u,0,j+j1-w,k+k1-w}+f_{u,0,j,k}\times f_{v,0,j1,k1}\times {j \choose w}\times{k+k1-w \choose k}$. For $f_{v,i,j,k}(i\neq 0)$, it won't interfere the transition with its following siblings. And for $f_{u,i,j,k}$, just consider where to put $u$. The answer for $i$ operations is $f_{1,i,i-2,0}$. 中文版本对于树上选一个点删去一个子树方案数这个经典问题，一个常见的 dp 是记 $dp_{u,k}$ 为 $u$ 子树选 $k$ 个点方案数，转移时兄弟间用组合数将其合并，然后祖先要选就必须选在它们前面，这一部分 $O(n^2)$。 回到本题，由于存在“自动删点”的过程因此我们不能将 $u$ 子树内选的点看成只有相对顺序的操作，因为其可能不合法。但我们考虑最终的操作序列，没有的位置留空：比如样例 $1$ 中第一次选 $4$，第二次选 $3$，第三次选 $1$，那么操作序列即为 $0 4 3 1$。也就是第 $i$ 次选的点放在 $n-i+1$ 的位置上。这样，我们发现一个点 $u$ 只能填在 $u$ 及以后的位置，那么对于一个点 $u$ 的子树，其 dfs 序区间为 $[l,r]$，那么 $u$ 子树的点填到 $r$ 以后的位置一定合法，而 $u$ 留的空其前面的兄弟和祖先填进去只要没有父子关系干扰一定合法，于是我们考虑 dp。 考虑一个 dp $f_{u,i,j,k}$ 表示 $u$ 子树 $i$ 这个位置留给祖先（也就是说 $i$ 及以前不能放东西，如果 $i=0$ 就不留），有 $j$ 个空（不包含给祖先留的），有 $k$ 个点要填到 $u$ 子树以后的位置。先考虑 $i=0$ 情况。那么合并两个子树的时候就是 dfs 序更小的子树可以选一些向后的操作填到 dfs 序更大子树的空里面。然后两个子树的空合并，向后操作合并。 具体来说，考虑 $u$ 的儿子按 dfs 序倒序枚举，对于一个儿子 $v$，那么合并 $f_{u,0,j,k}$ 和 $f_{v,0,j1,k1}$ 的时候先枚举一个 $w$ 代表选多少个 $v$ 中的向后操作填到 $u$ 的 $v$ 之后的子树，转移即为 $f_{u,0,j+j1-w,k+k1-w}\leftarrow f_{u,0,j+j1-w,k+k1-w}+f_{u,0,j,k}\times f_{v,0,j1,k1}\times {j \choose w}\times{k+k1-w \choose k}$。 再考虑 $f_{v,i,j1,k1}$ ，发现它需要给祖先留空并不影响其和后面兄弟的转移，因此转移同上，只是 $v$ 留的空 $u$ 同样需要留，所以转移到 $f_{u,i,j+j1-w,k+k1-w}$。注意这里需要预处理转移系数（因为 $i$ 取任何值转移系数相同）才能达到 $O(n^5)$。 然后考虑 $f_{u,i,j,k}$ 的转移，即 $v$ 后面的子树已经留了空。那么 $v$ 子树现在不能放任何东西，但是可以用一些向后的操作填 $i$ 后面的空，这里用 $dp_{v,k}$ 去转移即可。 子树转移完后，接下来是 $u$ 自身的操作。$u$ 可以有几种选择：
最后求答案的时候，对于要求 $k$ 次操作，相当于给 $1$ 在 $n-k+1$ 的位置留了空，同时恰好只有 $n-k$ 个空（那么后面就没有空，就是合法的操作序列），输出即可。
题目4286 [THUPC 2025 Final] I’m Here
AAAAAAAAAAAAA
评论
2026-01-29 18:39:27
|