Day47【最小生成树】

题目链接们

色

首先不难发现答案一定是某条边的权值，且该边两个端点的颜色不同。

类似于 CSP2022S-星战的思路，我们把 $m$ 条边先排序，再分为 $\sqrt m$ 个块，并定义边 $i$ 的 Hash 权值为 $(col_u - col_v) \times w_i$ ，如果一个块内所有边的权值累和为 $0$ ，那么当前块内没有我们想要的边，否则如果有，暴力遍历当前块即可。

至于维护动态维护块 Hash 的值，先预先记录一下当前点的出边权值和与入边权值和即可，有手就行。
时间复杂度： $\times \sqrt m)$

最小公倍树

不难发现复杂度瓶颈在于边数太多，所以考虑缩减边的规模。

考虑一个点序列 ${a,b,c,d,....,e,f,g\}$ ，不失一般性地钦定 $a < b < c < d < e < f < g$ ，如果该序列两两 $\gcd$ 相等，那么只需要连边 $(a, b)$ ， $(b, c)$ ,… , $(f, g)$ 即可，这就把边的规模缩减为 $O(n\ln n)$ 。

剩下的暴力 kruscal 即可。

Power Tree

好题，好题。

首先一眼看出树形结构没有用，求出每个点支配的叶子区间 $l_i,r_i]$ 即可弃用树型结构。

不妨令叶子节点权值的差分数组为 $e$ ，那么 Alice 的操作实际上是： $e_{l_i} \leftarrow e_{l_i}+v$ ， $e_{r_i+1} \leftarrow e_{r_i+1}-v$ 。

接下来就是最小生成树的典中典结论，考虑把操作 $l_i,r_i+1)$ 视为一条边，那么若两个点 $u, v$ 联通，就意味着我们可以通过若干操作，达到直接操作 $(u, v)$ 的效果。

那么题目条件等价于选择一些边 $l_i,r_i+1)$ ，使得差分数组 $e$ 的 $n + 1$ 个点联通，跑 kruscal 即可。
然而这道题要求所有方案的并集，所以权值相等的边要一起考虑，这一点很重要。

City 城市建设

好题，好题。

最近一个月已经见过三次这道题了。还有一次 noip 模拟赛考到这道题，赚麻了。

我们考虑线段树分治处理询问，假设当前处理到询问 $[l, r]$ 。现有如下两个 $t r i c k$ ：

我们把询问 $[l, r]$ 中涉及到的边的边权强制置为 $in f$ ，跑一遍 kruscal，那么不在当前最小生成树上的边，一定不会在其子区间的最小生成树上出现，我们直接把这些边删去即可。
再考虑把 $[l, r]$ 中涉及的边的边权强制置为 $- in f$ ，再跑一遍 kruscal，如果此时出现在最小生成树上的边权不为 $- in f$ 的边，一定会出现在其子区间的最小生成树上，我们直接把这些边 $U ni o n S e t$ 并累加这些边的贡献即可。

如果说人话就是，此题线段树分治的实质是时间分治，每个线段树节点都对应了一个最小生成树，如果把接下来可能边权会变的边置为极大值，那么就是在最好情况下， $e\in [l_i,r_i]$ 这些边的出现情况，如果还不出现，那么就意味着，接下来无论怎么修改，这些边肯定不会出现，置为极小值也同理对应着最坏情况，如果这些边还出现了，那么无论接下来怎么修改 $\in [l_i,r_i]$ 这些边的边权，它们都会出现。

不难发现第二种操作把点的规模缩减为了 $O (r - l)$ ，而第一种操作把边的规模缩减为了 $O (r - l)$ ，这样每个区间暴力跑 kruscal 的时间复杂度是对的。

具体实现上，对于每个线段树节点 $p$ 求出其对应的询问区间 $l_p,r_p]$ 涉及到的边集 $E_q$ ，然后每次递归时，维护一个当前边集 $E$ ，每次处理时，暴力把 $E_q$ 中的边置为极端值，然后用 $E$ 中的边跑 kruscal，得到新的边集 $E_{nxt}$ ，然后下放 $E_{nxt}$ ，递归左右区间即可。

递归到叶子节点时修改边权，计算答案，线段树分治回撤时，用可撤销并查集即可。

时间复杂度： $\log n \log q)$

新年的繁荣

一眼 Brovaka 板子题，把板子复制下来改到一半发现 Trie 树处理不了形如 $a_i \& a_j$ 这种形式的式子？？？

事实证明可以，如果当前位为 $1$ ，往 $1$ 方向递归即可，如果当前位为 $0$ ，先预先把 $1$ 方向的节点复制一遍丢到 $0$ 方向里，然后递归 $0$ 方向即可，好像时间复杂度是对的，但我不太会这种做法。

考虑针对于这道题的做法，注意到边权范围只有 $0 , 2^{20})$ ，那么我们完全可以枚举边权。

首先把相同的数先合在一起，这显然是最优秀的，那么剩下来若干个互不相同的元素，我们枚举从大到小枚举边权 $i$ ，然后枚举满足 $a_x \& a_y = i$ 的二元组 $(x, y)$ ，然而这样复杂度是 $O(n^3)$ 的，无法接受。

接下来考虑抽象的做法，假如说当前枚举到边权 $i$ ，那么满足 $popcount(a_x) = popcount(i)+1$ 的 $a_x$ ，实质上可以直接视为 $i$ ，那么我们转而枚举满足这样性质的 $(x, y)$ ，如果 $a$ 中原来没有 $i$ ，那么随便找一个 $a_x$ 变成 $i$ 即可，然后把这些 $x, y$ 全部 $U ni o n S e t$ 就完事了。

简要说一下正确性，因为我们从大到小枚举边权，所以要尽可能多的连这样的边，类似于或者说就是 Brovaka，而 $a_x$ 直接变为 $i$ 这种看似错误的操作，实际上是合法的，因为任意 $a$ 中的元素被视为其二进制意义下的某个子集，不会使答案更优的。

免费道路

先自然想到一个假思路，把边顺序 random_shuffle 若干次然后跑生成树，发现已经有 $k$ 条黑边了就停止加入黑边即可。

没试过，但正确率应该感人，为什么，因为图可能不连通，又是为什么，考虑一个问题：有些黑边是必须加的，换个意思说，不加这些黑边图联通不了！！！

所以我们先跑一边生成树，把白边先全加进去，再把黑边加进去，此时加入的黑边就是必须加的，然而这样有一个思维小漏洞，必须加入的黑边组成的集合不是唯一的，但我们任选其中一个集合是对的，为什么？因为无论选其中哪个集合，都能在最坏情况下保证图联通，满足了我们的最初目的。

接下来再跑一遍生成树，把这些黑边先加进去，再优先把剩余黑边往里面加，再加白边，最后判断一下黑边数量是否达到 $k$ 条即可。

Sorting a Grid

好题，好题。

注意到 $C$ 变为 $D$ 的操作，“每一行任意排列”，那么行内的相对顺序是不重要的，这启发我们把在 $D$ 矩阵中同一行的元素染成同一颜色，那么我们只需保证 $C$ 矩阵每一行的颜色相同，就可以保证 $\rightarrow D$ 。

接下来考虑 $\rightarrow C$ ，“每一列任意排列”，显然，我们只需要保证 $B$ 矩阵每一列中每一种颜色恰好出现一次，那么 $B$ 一定可以变为 $C$ 。

那么原问题等价于，现在有一个 $A$ 矩阵，其中有 $n$ 种颜色，每种颜色恰有 $m$ 个，现在我们对每一行任意排列，使得 $A$ 矩阵每一列中每一种颜色恰好出现一次。

二分图典中典 $t r i c k$ 。把每一行向其包含的颜色连边，然后我们对每一列跑 $m$ 次完美匹配，根据 Holl 定理易证明每次都是完美匹配。对于一个大小为 $n$ 的匹配，其具体含义就意味着第 $i$ 行，当前列的颜色为 $ma t c h [i]$ ，由此我们求出了 $B$ 矩阵，由 $B$ 推 $C$ 应该人人都会吧。

这里简单用 Holl 定理证明一下，假设当前已经处理完了 $k$ 列，对于左部点的一个子集 $S$ ，其有一个邻点集和 $S_v$ ，且 $S$ 向 $S_v$ 有 $\times |S|$ 条边，并且 $S_v$ 中每个点的度数最多为 $m - k$ （最开始为 $k$ ，每次完美匹配减 $1$ ），所以一定有 $\le |S_v|$ ，得证。