A. 寄（post） 对于点对贡献问题考虑在最近公共祖先处计算答案，称给定的 $m$ 个点为关键点，选择的 $k$ 个点为选择点。 既然我们已经要求了对于每一对关键点和选择点均在其最近公共祖先处计算答案，那么这也就意味着，存在某些节点，其子树中的关键点 / 选择点不会与其子树内的选择点 / 关键点配对。我们可以发现：若某节点子树内的关键点未与其子树内的选择点配对，那么产生的花费只与未配对的关键点数量有关；若某节点子树内的选择点未与其子树内的关键点配对，那么产生的花费只与其到子树根节点的距离有关，因此对于任意节点，其子树内将要与子树外的关键点配对的选择点只会存在一个最优选择。同时我们可以发现，对于任意节点，在考虑以其为最近公共祖先的点对时，每个儿子节点的子树不可能同时有未匹配的关键点和未匹配的选择点，否则这种情况一定不是最优情况。因此我们可以对上述两种情况进行 DP。 设 $f_{u, i}$ 表示 $u$ 子树内恰好存在 $i$ 个关键点未配对的最小花费。$g_{u, v}$ 表示 $u$ 子树内不存在未配对的关键点且已经选择了点 $v$ 作为与子树外的关键点进行配对的最小花费。使用类似于树上背包的转移即可。 复杂度为 $\mathcal{O}(n^2)$。 Code #include <bits/stdc++.h> typedef long long valueType; typedef std::vector<valueType> ValueVector; typedef std::vector<ValueVector> ValueMatrix; typedef std::pair<valueType, valueType> ValuePair; typedef std::vector<ValuePair> PairVector; typedef std::vector<PairVector> PairMatrix; constexpr valueType MAX = std::numeric_limits<valueType>::max() >> 2; valueType N, M, C; ValueVector Count; PairMatrix Tree; ValueVector Dist; ValueMatrix F, G; void dfs(valueType x, valueType from) { F[x][0] = C; F[x][Count[x]] = 0; G[x][x] = C; for (auto const &[to, w] : Tree[x]) { if (to == from) continue; Dist[to] = Dist[x] + w; dfs(to, x); ValueVector NextF(Count[x] + Count[to] + 1, MAX), NextG(N + 1, MAX); for (valueType i = 0; i <= Count[x]; ++i) for (valueType j = 0; j <= Count[to]; ++j) NextF[i + j] = std::min(NextF[i + j], F[x][i] + F[to][j] + w * j); for (valueType i = 1; i <= N; ++i) { if (G[x][i] == MAX) continue; for (valueType j = 0; j <= Count[to]; ++j) NextG[i] = std::min(NextG[i], G[x][i] + F[to][j] + (Dist[i] - Dist[x] + w) * j); NextF[0] = std::min(NextF[0], NextG[i]); } for (valueType i = 1; i <= N; ++i) { if (G[to][i] == MAX) continue; for (valueType j = 0; j <= Count[x]; ++j) NextG[i] = std::min(NextG[i], G[to][i] + F[x][j] + (Dist[i] - Dist[x]) * j); NextF[0] = std::min(NextF[0], NextG[i]); } F[x]....

A. 枇杷树 考虑从增量的角度计算答案，若我们在构造树 $T_n$ 时已经得到了树 $T_x$ 和 树 $T_y$ 的答案 $Ans_x$ 和 $Ans_y$，我们考虑如何得出 $Ans_n$。 考虑 $Ans_n$ 与 $Ans_x + Ans_y$，发现即为跨越新增的边的所有路径权值之和。其可以表达为： $$f(x, u) \times size_y + f(y, v) \times size_x + w \times size_x \times size_y$$ 其中 $f(n, p) = \sum\limits_{0 \le i < size_n} \operatorname{dist}(p, i)$ 即在 $T_n$ 中 $p$ 与所有节点的距离之和。考虑如何求出 $f(n, p)$，不妨通过递归求出，考虑 $p$ 在哪棵树中，那么另一棵子树的贡献可以拆分为连接点到其所有节点的距离之和再加上连接点到 $p$ 的距离即可，不妨设 $p$ 在 $T_x$ 中，那么我们有： $$f(n, p) = f(x, p) + f(y, v) + g(n, x, v) \times size_y$$...

[ABC308G] Minimum Xor Pair Query 将所有数放在 0-1 trie 上，考虑对于一个数 $x$ 查询在数集中与其异或和最小的数的过程，发现最终查询到的数在 0-1 trie 的 dfs 序上一定与之相邻。而 0-1 trie 的 dfs 序就是叶子节点按升序排序后的值。 因此我们只需要维护出每个数与在其数集中的前驱和后继的异或和即可，查询时取这些异或和的最小值即可更新答案。 复杂度为 $\mathcal{O}(Q \log Q)$。 [ARC169D] Add to Make a Permutation 考虑去除 $A_i$ 对 $N$ 取模的限制，现在问题转化为了使得 $A_i \bmod N$ 的值两两不同。 首先我们考虑对于一个序列 $B$，$A$ 可以在经过若干次操作后得到其的充要条件是什么： $A_i \le B_i$ $\sum\limits_{i}\left(B_i - A_i\right) \mid M$ $\forall i \rightarrow B_i - A_i \le \frac{\sum\limits_{i}\left(B_i - A_i\right)}{M}$ 我们将 $A$ 按升序排列，接下来我们尝试证明最优的 $B$ 一定是 $\left(x, x + 1, \cdots, x + N - 1\right)$ 经过重排后得到的。其中 $x$ 为 $B$ 序列的最小元素。...

DP 套 DP 的题目一般大致要求为求满足某个要求的元素数量。而对于其要求的判定需要 DP 来解决。因此我们将判定 DP 的结果作为计数 DP 的状态来进行计数。 [TJOI2018] 游园会 首先考虑如何求出两个字符串 $S, T$ 的 LCS，设 $f_{i, j}$ 表示 $S\left[1, i\right]$ 和 $T\left[1, j\right]$ 的 LCS 长度。发现其有如下转移： $$f_{i, j} = \begin{cases} f_{i - 1, j - 1} + 1 && S_i = T_j \ \max\left{f_{i, j - 1}, f_{i- 1, j}\right} && S_i \neq T_j \end{cases}$$ 我们考虑对上述判定 DP 的过程进行计数，具体的，将上述判定 DP 结果相同的前缀作为相同的子问题进行合并后计数以优化复杂度，但是若直接对于某个 $i$ 将所有的 $f_{i, j}$ 值均压入状态那么状态数为 $\mathcal{O}(N \times K^K)$，无法接受，需要进一步发掘性质。...

A. 小明修公路 对于每新增的一条边权为 $w$ 的路径 $\left(u, v\right)$，我们尝试用其去更新 $d$ 矩阵的值。 具体的，枚举 $x, y$，有： $$d_{x, y} \leftarrow \min\left{d_{x, u} + w + d_{v, y}, d_{x, v} + w + d_{u, y}\right}$$ 复杂度 $\mathcal{O}(n^2k)$。 B. 小明的字符串 设 $f_{i, j}$ 表示考虑到 $s$ 的前 $i$ 个字符且 $s_i$ 匹配到 $t$ 的第 $j$ 个字符的情况下 $t$ 的出现次数。预处理出 $\operatorname{transfer}\left(l, c\right)$ 表示在匹配到 $T$ 的第 $l$ 个字符的情况下在添加一个 $c$ 字符可以匹配到 $T$ 的第几个字符。使用 KMP 预处理即可，进而可以直接转移。 发现其实质上为自动机 DP，内层自动机为 KMP 自动机。 复杂度为 $\mathcal{O}(\left\lvert S\right\rvert \left\lvert T\right\rvert \left\lvert\Sigma\right\rvert)$。...

A. 开心消消乐 首先考虑给定字符串如何判定是否合法。设 $f_{i, 0 / 1, 0 / 1}$ 表示在前缀 $i$ 位后添加一个 $0 / 1$ 是否可以使得其变为 $0 / 1$，$f$ 有意义当且仅当 $i$ 为偶数。 考虑如何转移，即从 $f_{i - 2, 0 / 1, 0 / 1}$ 转移到 $f_{i, 0 / 1, 0 / 1}$。 记 $x = s_{i - 1}, y = s_{i}$ 考虑枚举要添加的值 $z$ 和要转化的值 $t$，那么我们要转移到的状态记为 $f_{i, z, t}$。 那么我们在转移的过程中按选取的前缀顺序考虑如下两种情况： 选取前缀 $i - 1$，即根据 $f_{i - 2, x, 0 / 1}$ 的值加上 $y, z$ 的值考虑其是否可以消为 $t$。 选取前缀 $i + 1$，即先将 $x, y, z$ 合并，之后与 $f_{i - 2, x, 0 / 1}$ 合并得到结果。 处理出 $f_{n - 1, 0 / 1, 0 / 1}$ 的值后将 $s_n$ 与之合并即可得到答案。...

CF1778F Maximizing Root 首先不难证明不操作根节点一定不优，因此我们考虑操作根节点的情况。 现在我们的问题转化为了：最大化操作根节点前的整个树的节点权值的最大公约数。 由于可能的最大公约数值只有 $\mathcal{O}(\sqrt{V})$ 种。因此我们考虑将其压入状态进行动态规划。 设 $f_{u, j}$ 表示使得 $u$ 子树内的所有节点点权和根节点点权最大公约数为 $j$ 的最小操作次数。转移时枚举子树的最大公约数即可，复杂度为 $\mathcal{O}(n \sqrt{V}^2) = \mathcal{O}(nV)$，可以通过。 Code #include <bits/stdc++.h> typedef long long valueType; typedef std::vector<valueType> ValueVector; typedef std::vector<ValueVector> ValueMatrix; typedef std::unordered_map<valueType, valueType> ValueMap; constexpr valueType MAX = std::numeric_limits<valueType>::max() >> 20; valueType N, K; ValueVector Factor, A; ValueMap Map; ValueMatrix G, F; void calc(valueType x, valueType from) { for (auto const &to : G[x]) { if (to == from) continue; calc(to, x); for (valueType i = 0; i < Factor....

定义 首先定义无向图的边着色。 对无向图 $G$ 的边着色，要求相邻的边涂不同种颜色。 若 $G$ 是 $k$ - 边可着色的，但不是 $\left(k - 1\right)$ - 边可着色的，则称 $k$ 是 $G$ 的边色数。记为 $\chi^{\prime}\left(G\right)$。 Vizing 定理 若 $G$ 是简单图，那么有 $\Delta \left(G\right) \le \chi^{\prime}\left(G\right) \le \Delta \left(G\right) + 1$。 若 $G$ 是二分图，那么有 $\chi^{\prime}\left(G\right) = \Delta \left(G\right)$。 其中 $\Delta \left(G\right)$ 为 $G$ 的最大度数。 对于简单图的最优边染色方案仍然是 NP-hard 的，因此我们主要考虑 $G$ 为二分图的情况。 该定理存在两种证明方法，下面依次给出。 对 $\Delta G$ 进行归纳 对于 $D = 0$ 的情况，上述定理成立。 对于 $D > 0$ 的情况，我们考虑将二分图 $G$ 划分为一组匹配 $M$ 和子图 $G \setminus M$。且 $\Delta \left(G \setminus M\right) = \Delta \left(G\right) - 1$。...

[MtOI2018] 情侣？给我烧了！ 设 $f_{k, n}$ 表示在有 $n$ 对情侣的情况下钦定 $k$ 对情侣是和睦的方案数，$g_{k, n}$ 表示在有 $n$ 对情侣的情况下恰好有 $k$ 对情侣是和睦的方案数。考察二者之间的关系，我们有： $$f_{k, n} = \sum\limits_{m = k}^{n} \dbinom{m}{k} g_{m, n}$$ 根据二项式反演，我们有： $$g_{k, n} = \sum\limits_{m = k}^{n} \left(-1\right)^{m - k} \dbinom{m}{k} f_{m, n}$$ 考虑如何求出 $f_{k, n}$，我们有： $$f_{k, n} = \dbinom{n}{k} \times n^{\underline k} \times 2^k \times \left(2n - 2k\right)!$$ 上述式子的含义是：首先从 $n$ 对情侣中选出 $k$ 对情侣，然后将这 $k$ 对情侣钦定为和睦的，然后将这 $k$ 对情侣的位置确定下来，最后将剩下的 $2n - 2k$ 个人的位置确定下来。 代入上述关系式，我们有： $$\begin{aligned} g_{k, n} =& \sum\limits_{m = k}^{n} \left(-1\right)^{m - k} \dbinom{m}{k} \times \dbinom{n}{m} \times n^{\underline m} \times 2^m \times \left(2n - 2m\right)!...