比赛链接

Upsolved by nikkukun.

推荐购买《Portal》及《Portal 2》以加深题目理解

给一个 $n \leq 300$ 点的带权无向连通图，有 $k \leq 300$ 个任务，第 $i$ 个任务需要从 $a_i$ 移动到 $b_i$。当你经过某个节点时，你可以在此打开一个传送门，同一时刻最多只有两个传送门，且你可以随时随地关闭它们。

求完成所有任务的最短路径和。

可以发现实际上是依次经过 $2k$ 个关键点 $c_1, c_2, \ldots, c_{2k}$ 的任务。

官方题解提供了其他两种复杂度不对，但是具有启发意义的解法：

1. $f(i, u, a, b)$：完成前 $i$ 个任务，目前在 $u$，两个传送门在 $a$ 和 $b$。由于转移有环，需要用 Dijkstra；
2. $f(i, u, a)$：完成前 $i$ 个任务，目前在 $u$，当前位置有一个传送门，另一个在 $a$。状态的化简是基于传送门一定是用的时候当场打开的观察的。

正解还可以继续精简状态：$f(i, a)$ 表示完成前 $i$ 个任务且站在结束节点上，当前令一个传送门在 $a$。状态的化简是基于一次任务只会改变最多一次传送门的观察的。这样枚举本次任务后传送门变为 $b$，有三种转移：

1. $c_i \to c_{i+1}$，不用传送门；
2. $c_i \to a \to b \to c_{i+1}$，使用传送门到 $a$，然后经过 $b$ 时建立传送门；
3. $c_i \to b \to a \to c_{i+1}$，经过 $b$ 时建立传送门，然后使用传送门到 $a$。

总时间复杂度 $O(kn^2)$。

Solved by nikkukun.

给一个非负权的树，你可以任意加边或删边，但任意时刻要保证：

1. 连通
2. 任意环异或和为 $0$

求操作过后整棵树的最小权。

不难发现将边权往小修改的操作其实很像最小生成树的过程（接一个环，去掉环上的最大边），又发现这个图实际上一直是一棵生成树，其边权 $(u, v)$ 是原图中 $u \to v$ 的路径异或和，因此只要求这个图的 MST 即可。显然，令 $d(u)$ 为 $u$ 到根的路径异或和，则 $d(u) \oplus d(v)$ 就是 $u \to v$ 的路径异或和。

剩下的就是 老原题 了。考虑 Kruskal 过程从小到大连边：将所有 $d(i)$ 插入 trie 中，先给子树建好 MST，再往上合并两子树的 MST。合并的过程是要找两个子树中异或的最小值，这个可以暴力在两个子树中递归。由于每个节点只会被暴力搜到 $O(\log V)$ 次，因此总复杂度是正确的。如果不放心，也可以启发式合并维护一个子树的值，用另一个子树去查询最小值。

Upsolved by nikkukun.

两个正整数序列 $a_1, a_2, \ldots, a_k$ 和 $b_1, b_2, \ldots, b_k$ 满足 $\sum _{i=1}^k a_i = n,\ \sum _{i=1}^k b_i = m$。对于两序列所有可能的情况，求

$$ \prod _{i=1}^k \min (a_i, b_i) $$

之和。其中 $1 \leq n, m \leq 10^6$，$1 \leq k \leq \min(n, m)$。

首先要将 $\min$ 转化为其他方便统计的东西，通常的做法是 $\min (a, b) = \sum_{i = 1} ^{\infty} [i \leq a] \cdot [i \leq b]$ 这样拆，进而变成对额外变量的统计。这个技巧在 CF 1292C 也有类似应用：

关于一个树上 mex 的推论：
$$ \begin{aligned} S &= \sum_{1 \leq u < v \leq n} \mathrm{mex}(u, v) \\ &= \sum_{1 \leq x \leq n} \left( \sum_{\mathrm{mex}(u, v) = x} x \right) \\ &= \sum_{1 \leq x \leq n} \left( \sum_{\mathrm{mex}(u, v) \geq x} 1 \right) \\ &= \sum_{1 \leq x \leq n} f(x) \\ \end{aligned} $$
其中 $f(x)$ 是满足 $\mathrm{mex}(u, v) \geq x$ 的二元组个数。

即是说 $\mathrm{mex}$ 和 $\min$ 操作都可以用类似方法解决。因此本题有

$$ \begin{aligned} \prod _{i=1}^k \min (a_i, b_i) = \prod _{i=1}^k \sum _{c_i=1}^{\infty} [c_i \leq a_i] \cdot [c_i \leq b_i] \end{aligned} $$

后面的和式代表 $i$ 位置上 $(a_i, b_i, c_i)$ 三元组的合法种类，故由乘法原理可以知道式子实际是对满足条件的 $(\{a_n\}, \{b_n\}, \{c_n\})$ 三元组计数。不妨钦定 $n \leq m$，且枚举 $x = \sum_{i=1}^k c_i,\ x \in [k, n]$，则插板法得到满足条件的 $\{a_n\}$ 个数为 $\binom {n - x + k - 1}{k -1}$，故可以计算最终答案为

$$ \sum _{x=k}^n \binom{n - x + k - 1}{k - 1} \binom{m - x + k - 1}{k - 1} \binom{x - 1}{k - 1} $$

总时间复杂度 $O(T\min(n, m))$。

Solved by Potassium.

水题不表。

Solved by nikkukun.

水题不表。