题解：P11363 [NOIP2024] 树的遍历

· · 题解

来一个考场上半个小时不到会了但是花了将近一个小时实现的复杂做法。

这个题面看着就很吓人，把边当点连出一堆边，给定若干个特殊点作为根，求本质不同 dfs 生成树个数。乍一看好像很像 NOI2023 D1T3，但是这个题看上去有很强的特殊性质。

考虑菊花图的部分分，这相当于把边集连成完全图。经过小量手玩可以发现最终的生成树一定形如一条链。而树根的限制则相当于必然存在一个链的端点恰好是一个特殊点。因为从根遍历下去如果还没访问完所有的点则一定没访问完当前最后一个点的邻点，于是形成一条链。答案容易用容斥计算，钦定两个端点都不是特殊点即可。于是答案只和 n,k 相关。

考虑一般图，建出边代表的图可以发现，这个图缩点之后大概很有性质。点双缩点之后可以发现得到了原树（把原来的点作为方点，边作为圆点得到了新图的圆方树）。同菊花一样考虑，可以发现每个点双内（即每个点周围的所有边）在生成树中一定连通且导出子图形如一条链。

考虑对于一个非叶子节点刻画它的 dg 条邻边形成的链，可以发现只需要确定链的两个端点，其余的方案数是任意排布 dg-2 个点的顺序，方案数 (dg-2)!。于是只需要对于每个点选择周围的两条边即可。

考虑一条边如何可以成为 dfs 树的根。注意到我们从根出发进入一个点双的入口是唯一的，也就是要求必须选择那条指向根的边。于是任意得到 k=1 的答案，除了一条必选边其余随便选，方案数 \prod (dg-1)，再乘上刚才的阶乘积。

先考虑到父亲的边要选择的情况，设令一条边连接 $y$，则合并所有状态 $f(son_i,p_i,q_i)$ 可以得到的 $p=1$ 当且仅当： - 到父亲的边是特殊边或到 $y$ 的边是特殊边。 - 且除了 $y$ 的其他儿子的 $q=0$。 得到的 $q$ 是所有儿子的 $q_i$ 的或。考虑背包合并，$g(0/1,0/1,0/1)$ 表示当前是否选择了点 $y$，以及当前合并得到的 $p,q$ 的值。 再考虑父亲的边不选择的情况，此时一定有 $q=1$，用类似上述的背包同样可以转移：$h(0/1/2,0/1,0/1)$ 表示当前钦定了的儿子个数，两个儿子是否分别满足限制。 两个转移仅仅带了一百多的常数，在 $\sum n\le 10^6$ 的情况下可以轻松通过，时间复杂度是 $O(n)$ 的。 可以发现这个做法代码超级难写，又没有代码公示，所以贴不了了。