最后一次 拥抱我吧
哪怕只有海风
——洛天依《海边城》
Boruvka
适用于处理求一个完全图的最小生成树，每条边的边权具有某种特殊性质，且容易求出一个点到其它所有点中的最小边权。
一个常用 trick：当不好处理最小边与当前的点 \(i\) 是否在同一连通块时，可以考虑对于每个 \(i\)，求出最小值 和 与最小值不在同一连通块内的次小值，这样可以保证两个里面一定有一个和 \(i\) 不在同一连通块内。
天依宝宝可爱！
CF888G
思维难度：\(\color{#52C41A} 绿\) *1700
对于一个完全图求 MST，点数到达了 \(10^5\) 的级别，于是不能用常规的 Kruskal 做了。
但是这些边有特殊性质！
引入一个有点奇怪的算法：Boruvka。
考虑现在已经确定了 MST 上的一些连通块，那么接下来就要合并这些连通块（加边）。显然加的边的边权越小越好，那么如果可以通过某种手段找到每个连通块连向外面的最小边，那么连这条边对于这个连通块来说一定是最优的，而又因为一个连通块一定会往外面连一条边，所以这条边一定在 MST 内。
考虑最坏情况，就是连通块之间两两互相连了最小边，这样一轮操作会使连通块数减半，所以最多迭代 log 次，即时间复杂度为 \(O(n \log n)\)。
然后就是如何找最小边了，一般是要根据题目中图的某个特殊性质，通过一些手段找到。
回到这个题，边权是点权的异或和，又要求最小边，于是很自然地想到 01trie。然后就简单了，对于每个连通块分别查找连通块内每个点和外部的点的最小异或和再取 min 就可以了，这个在 01trie 上是容易的，复杂度 \(O(\log V)\)。显然每个点恰好被遍历一次，所以每轮操作复杂度 \(O(n \log V)\)。
故总复杂度 \(O(n \log n \log V)\)。
开了 set 存 trie 上每个点对应原图上的哪个点，然后被卡空间了/fn
发现每个点都开个 set 是很浪费的，因为只有叶子结点会有数，所以只在叶子结点开就可以，这样只需要开 \(O(n)\) 个 set。
然后发现上面的做法还是太糖了，其实可以直接先对 \(a_i\) 去重，然后就不需要开 set 了，因为同一个数最多只能对应一个位置。。。
然后又被卡常了（）应该是每次暴力删点加点，log 跑得太满导致的。
根据题解区，有启发式合并的，有虚树单 log 的，还有用 Kruskal 的……但是根据这篇题解，找到一些结论之后问题会变得很简单的。
主体思想还是不变，就是 Boruvka + 01trie，但是不显式地去写 Boruvka。注意到在 trie 上，如果将所有点按照最高不同位（即最高的同时有 \(0\) 的点和 \(1\) 的点的位置）切成两半，那么 Boruvka 的过程中一定是先把两半分别建好，再在两半之间加边。
这启示我们可以把 Boruvka 倒过来做，甚至按照任意顺序做，因为两半分别的答案与两半之间的答案是没有任何关联的。
还有，再这个过程中，我们可以不用暴力删点加点了，只需要控制前缀相同就可以了！
到这里已经可以了，但是还是避免不了显式地写 Boruvka，虽然没什么坏处，但也没什么好处（）
可以注意到，上面过程中切成的两半一定满足 \(0\) 的一半小于 \(1\) 的一半，所以给序列排个序就可以直接在序列上做了。这样我们就成功地把一个很图论的图论题转化成了数列上的题。
然后甚至不需要在 trie 中记录 siz 和 cnt 了，只需要记录每个节点控制的区间端点即可。
虽然复杂度还是 \(O(n \log n \log V)\)，但是显然常数非常非常小。
算是加深了对 trie 的理解了，别问为什么。
submission
天依宝宝可爱！
UOJ 176
思维难度：\(\color{#52C41A} 绿\) *1900
看起来和上一题几乎一样……
但是发现这个东西在 trie 上好像根本没法做，因为按位与不好贪心，遇到当前位为 \(0\) 的时候无法确定走哪棵子树，需要两棵子树都试一试。
所以可以考虑把一棵子树的信息复制到另一棵子树上，这样就可做了（）也不知道是怎么想到的
但是有上一题的教训，我决定直接放弃这个时间空间都有点爆炸的做法。
注意到 \(m \le 18\)，所以考虑 Kruskal 的过程从大到小加边。我们直接 \(O(2^m)\) 枚举边权 \(s\)，然后找到所有满足 \(a_i \land a_j = s\) 的 \(i,j\) 并合并。
然后就是很巧妙的地方了。因为直接枚举 \(i,j\) 是无法做到的，所以可以把每个已经枚举过的 \(a_i\) 传递到 \(a_i\) 的子集当中。注意到，在所有 \(a_i \or 2^x\) 中，是不会出现该位置是由 \(>1\) 个位置传递过来的，因为如果 \(a_i \or 2^x\) 同时是两个位置的子集，那么这两个位置与起来的值一定 \(>s\)，所以就已经在之前的过程中合并过了，于是就相当于只有一个位置传递过来了。
那么直接找到所有 \(>0\) 的互不相同的 \(a_i \or 2^x\) 位置，从随便找一个和其它的合并即可，复杂度是 \(O(m)\) 的。
还有一点，就是当原数组出现 \(a_i = a_j\) 的时候，需要特判。显然两者之间连边一定是最优的，调整法可以证明。
故总时间复杂度 \(O(2^m m)\)。
submission
天依宝宝可爱！
AT_keyence2019_e
思维难度：\(\color{#52C41A} 绿\) *1900
问题还是求一个点 \(i\) 到其它所有点的最小边权。
注意到绝对值很讨厌，所以考虑分讨来去掉，有：
于是和 \(i\) 有关的都放到了一块，所以开两棵线段树就可以解决了……
……吗？
显然再次根据第一题的教训，每次删点加点的常数是爆炸的。可以注意到对于不同的 \(i\)，如果不考虑连通块的限制，那么是可以 \(O(n)\) 预处理前缀最小值做的。
然后加上连通块的限制，发现也是可以维护的！对于每个点 \(i\) 我们维护两个信息 \(v_1 , v_2\)，\(v_1\) 是 \(1 \sim i{\color{#66CCFF} -1}\) 的最小值，\(v_2\) 是和 \(\color{#66CCFF} v_1\) 不在同一个连通块内的 \(1 \sim i{\color{#66CCFF} -1}\) 的最小值，这样 \(v_1 , v_2\) 中就一定有一个是和 \(i\) 不在同一连通块的。关于转移，若 \(i\) 的 \(v_1\) 和 \(i-1\) 的 \(v_1\) 在同一个连通块内，那么 \(i\) 的 \(v_2\) 一定为 \(i-1\) 的 \(v_2\) 和 \(i-1\) 中的一个；否则为 \(i-1\) 的 \(v_1\)。
复杂度 \(O(n \log n)\)，而且常数很小。
细节挺多的，传了 \(v_2\) 但忘记传 \(v_2p\) 硬控 2h！
submission
天依宝宝可爱！
AT_cf17_final_j
思维难度：\(\color{#FFC116} 黄\) *1400
怎么把最简单的放最后了（）
根据上题的 trick，只要求出树上到每个节点的最小值以及与最小值不在同一连通块内的次小值即可。显然可以树形 dp 求单个点再换根 dp 求整棵树。
有一个巧妙的地方，就是换根 dp 的时候不需要考虑 \(v\) 的子树被重复计算，甚至不用考虑 \(v\) 的答案中出现 \(v\) 这个点本身。前者是因为求的是最小值，故 \(v\) 子树中的点从 \(u\) 转移到 \(v\) 一定不如直接从 \(v\) 的子树中转移更优；后者是因为即使最小值 \(v\) 本身，那次小值一定不与 \(v\) 在同一连通块内。
submission
天依宝宝可爱！