P11363 [NOIP2024] 树的遍历

Cap1taL · 2024-11-30 17:54:45 · 个人记录

赛时做法

感性读题

首先如果把边全建出来，就变成了每个原图的点周围都包着一个完全图一样的东西

而我们大概要对于每一个完全图内部确定一个链，或者说确定一个遍历顺序，称为一个方案。我们要计数所有能从某个关键边开始遍历全图的方案

k=1

• 对于关键边的两个端点 u,v 所对应的完全图，它所在的完全图的链，链首必须是这个关键边，剩下的可以任意。方案数 (d_u-1)!(d_v-1)!

• 对于其他完全图，它们的链首也是确定的，就是关键边方向的父亲，这个稍微想一想应该可以发现。各自的方案数是 (d_u-1)!

• 因此 k=1 的总答案就是 \prod_u(d_u-1)!

一些必要的观察

当 k\neq 1 的时候，我们尝试观察：对于每一种给完全图确定链的方式，它能被哪些关键边统计

结合 k=1，可以发现，一个链的确定方案能被关键边 E 统计到，当且仅当：

分别以 E 的两个端点为根，设当前所在的点是 x，那么对于它的所有孩子 y，x 必须是 y 所在完全图的链的链首

因为链代表着遍历顺序，所以第一次被遍历到的一定是父亲，和 k=1 的情况很相似

平方 log

到现在还是有点抽象，但如果我们对于每个完全图，把它链的两个端点连接到完全图中心的原图点上，就会有些不一样

这是某个方案的连接：

可以看到存在一条从叶子到叶子的主路径。通过观察可以得知，这个链的确定方案只会被主路径上的关键边统计。换言之，如果一个方案的主路径上存在关键边，这个方案就会被计入答案。

所以我们可以枚举主路径，即枚举所有叶子对，把他们之间的简单路径当做主路径。

考虑对于一对确定的叶子，满足主路径是这个路径的方案有多少：

• 对于所有在主路径上的原图点 P，链首和链尾都是确定的，是主路径上的点。中间部分任意。方案数 \prod(d_P-2)!
• 对于所有不在主路径上的原图点 Q，链的一个端点是确定的，是主路径方向的父亲。其余部分任意。方案数 \prod(d_Q-1)!

因此我们有了一个 n^2\log 的做法：

• 随便预处理一下
• 枚举叶子对
• 求得 LCA ，确定主路径
• 检查主路径上是否有关键边，如果没有就跳过下面的步骤
• 计算主路径上点的 \prod(d-2)!，计算其他点的 \prod(d-1)!，乘起来加进总答案。可以随便差分着做。

单 log

这个做法很明显可以优化，这一步就很简单了，考虑 DP，或者说再简单预处理一下。