[AGC069D] Tree and Intervals
JWRuixi
·
·
题解
[AGC069D] Tree and Intervals
题意
对于一棵 n 个点的树，定义 a_i(1 \le i < n) := \sum\limits_{(u, v) \in E} [\min(u, v) \le i \land i < \max(u, v)]。
给定 n, P，求 n 个点的有标号无根树能生成多少中不同的 a 序列，输出答案对 P 取模的结果。
### 分析
转化太神奇了，感觉完全无法解释怎么想到的……
$a_i$ 实际上就是编号上跨过 $i$ 的边数。这个不好刻画，考虑类似差分的东西，记 $l_i$ 为从 $i$ 向左连的边数；$r_i$ 为从 $i$ 向右连的边数。那么可以发现 $a_i = \sum\limits_{j \le i} (r_j - l_j)$。
在转化的基础上考虑如何判定合法性，首先可以发现一些必要条件：
- 对于 $1 \le i \le n$，$l_i \ne 0$ 或 $r_i \ne 0$；特殊的，$l_1 = r_n = 0$；
- 显然有 $\sum\limits_{i \le n} l_i = \sum\limits_{i \le n} r_i = n - 1$；
- 由于 $l_1, \dots, l_i$ 描述的边构成了 $1, \dots, i$ 的生成森林，所以 $\sum\limits_{j \le i} l_j \le i - 1$；
- $1, \dots i$ 构成的连通块一定会和 $i + 1, \dots, n$ 连接在一起，所以每个连通块至少向后引出一条边，即对于 $1 \le i < n$，$a_i \ge i - \sum\limits_{j \le i} l_j$。
接下来我们将声称这是充要的。证明：我们称 $r_i$ 描述的边中尚未确定右端点的边为候选边，那么在确定 $l_i$ 描述的边的左端点时，我们优先考虑候选边数最多的连通块，按照这个策略就一定可以构造出合法的树了。
接下来考虑具体的计数，我们的核心问题在于多个 $\{l_n\}, \{r_n\}$ 序列可能对应同一个 $\{a_n\}$ 序列。经过观察我们发现我们对于 $r_i$ 的值没有具体的限制，也就是说 $r_i$ 可以随 $l_i$ 的需要进行调整，那么我们就只需要记录 $\sum\limits_{j \le i} l_j$ 的极值就可以保证无重了。
记 $dp_{i, j, k}$ 表示考虑了到 $i$，$a_i = j$、$\sum\limits_{t \le i} l_t$ 的最小值为 $k$ 的方案数。具体的转移就是枚举 $\sum\limits_{j < i} l_j$、 $a_{i - 1}$ 和 $a_i$，先不考虑限制计算出 $l_i$ 的最小值，此时可能不满足 $1 \le i - \sum\limits_{j < i} l_j \le a_i$ 的限制，不断增加 $l_i$（同时减小 $r_i$）进行调整只到符合限制。暴力转移 $\mathcal O(n^4)$。
优化考虑如果没有限制，则只存在三种转移：$l_i > 0, r_i = 0$ 或 $l_i = r_i = 1$ 或 $l_i = 0, r_i > 0$，这是可以用前缀和优化解决的。而我们的调整形如 $(j, k)$ 可以调整为 $(j + 1, k)$，所以我们可以先容许错误的转移，然后再整体进行调整。
复杂度 $\mathcal O(n^3)$。
### Code
提交记录：<https://atcoder.jp/contests/agc069/submissions/60180740>。