AGC009

A

从后往前加。

B

刚开始没看懂题意 WA 了两发 /qd

\(\rm dp\) 的时候把子树按照深度从小到大安排即可。

C \((\texttt{Easy} \ 2 / 1)\)

简单 \(\rm dp\) 题。

设 \(f_{0/1, i, j}\) 表示在前 \(i\) 个数里面选，第 \(i\) 个数在 \(A/B\) 集合内，另一个集合中最后选的数是第 \(j\) 个的方案数。

使用前缀和优化或线段树优化可以做到 \(\mathcal{O}(n)\) 或 \(\mathcal{O}(n \log n)\) 的时间复杂度。

D \((\texttt{Medium} \ 4 / 0)\)

我想到的唯一一个东西就是这个东西类似于点分治的过程，但是没什么用。

首先不难发现答案是 \(\log n\) 级别的。对于每个点，记录一下它被加进来的时间 \(t\)，那么对于一种方案，它合法当且仅当对于 \(\forall u, v\) 使得 \(t_u = t_v = x\)，\(u \to v\) 的路径上都存在一个点 \(w\)，使得 \(t_w > x\)。

所以我们考虑从叶子往根贪心选取。我们称一个节点被满足当且仅当其在目前的 \(\rm dfs\) 过程中已经确定了一个祖先节点，它的 \(t\) 值大于这个节点。每次 \(\rm dfs\) 一个点的时候，我们需要记录未被满足的点的时间集合，记为 \(s\)。确定 \(u\) 的 \(t\) 值的时候，我们需要考虑两种限制：

• \(t_u\) 不能在 \(s_v\) 中出现，否则 \(s_v\) 对应点到 \(u\) 的路径不满足了。
• 如果对于 \(v_1 \ne v_2\)，有 \(k \in s_{v_1} \cap s_{v_2}\)，那么 \(t_u > k\)，否则对应两点的路径不满足了。

把限制理清楚之后就可以直接贪心了。时间复杂度 \(\mathcal{O}(n)\)。

E \((\texttt{Easy} \ 3 / 0)\)

简单的 E 题。

考虑用类似 \(\rm Kruskal\) 重构树的方法把操作树建出来，那么深度为 \(i\) 的数 \(x\) 对答案的贡献就是 \(x \times k^{-i}\)。设 \(c_{i, 0/1}\) 表示深度为 \(i\) 的 \(0/1\) 的个数。

发现 \(c\) 不同，最后的答案不一定不同，原因是 \(c_{i, 0 / 1} \ge k\) 导致的，例如把 \(k\) 个 \(0\) 放在哪一层答案都一样。如果存在这种情况，可以看作是 \(0/1\) 的个数减少了 \(k - 1\)。

设 \(f_{d, t}\) 表示操作树深度为 \(d\)，钦定 \(c_{i, 0/1} < k\) 的不同数个数，\(1\) 的个数为 \(t\) 时的方案数。有了这个钦定的条件，操作树除了深度最大的非叶节点有 \(k\) 个叶子节点儿子外，其余的所有非叶节点都仅有 \(1\) 个非叶节点儿子，所以 \(0\) 的个数也是固定的，方案数可以通过简单 \(\rm dp\) 得出，最终的答案就是

\[\sum\limits_{i(k - 1) < n} \sum\limits_{j(k - 1) < m} f_{\frac{n + m - 1}{k - 1} - i - j, n - i(k - 1)} \]

时间复杂度 \(\mathcal{O}((n + m) ^ 2)\)。