一些构造
CF1464F Showing Off
显然原图连边会形成若干内向基环树森林，所有在同一个环上的点 \(S\) 是相同的，注意到原图是二分图，因此所有环都是偶环。
一个重要观察是，我们可以让所有环的长度都是 2，因为总可以把长度 \(> 2\) 的环拆成若干个二元环，而且在 \(S_{i, j} \geq 2\) 的限制下拆成二元环是最优的。
那么 \(S\) 相同且相邻的点可以形成二元环，假设钦定了二元环，那么环上显然可以取 \(1, S - 1\)，非环上的若存在一个 \(S\) 比它小的，则可以以 \(S\) 之差连边，否则这个点也必须形成环，否则无解。
因此二分图染色后，把可以匹配的点连边，对于一些点，可以参与匹配，对于另外一些点，必须参与匹配。因此跑有源汇上下界可行流即可。
虽然不是纯正的二分图匹配的 \(\mathcal O(n \sqrt n)\) 但是也能过？
CF1762F Tree Sum
首先得到 \(d_i + d_{i+ 1} - 2d_{anc_{i, i+1}} = w\)，然后非常神秘地我们考虑在模 \(2^k\) 意义下得到同余方程的解，因为 \(x \equiv w(\bmod p) \Leftrightarrow2 x \equiv 2w(\bmod 2p)\)，又 \(d_1 = 0\)，\(d_{i+1} \equiv w +2 d_{anc_{i, i+1}} - d_i \equiv w+(2(d_{anc_{i, i+1}}\bmod 2^k)) - d_i (b\mod 2^{k+1})\)，就可以递推求解，最后再检验即可。
CF1423C Dušan's Railway
*3500 就这？
首先直接令 \(k = 3\)，考虑序列上的问题：等价于先预处理一些区间，使得任意一个区间都可以由不超过 3 个预处理的区间得到。
当 \(k = 2\) 时就是猫树了，但是预处理的区间个数为 \(n \log n\) 级别，无法接受。
考虑 \(k = 3\) 是怎么拼出来的，可以想到分块的过程，两个不在同一块可以由一个后缀 + 整块对整块 + 前缀得到。但当两个元素在同一块内就寄了，考虑对每块内部继续分块，递归这个过程，次数不超过 \(\log \log n\) 次。
在树上就树分块即可，使用随机撒点的树分块，每块期望大小 \(\mathcal O(\sqrt n)\)，其实不满。
但是我被 wa on #7 了是怎么会是呢？
CF1299E So Mean
这个 *3400 和上面一个 *3500，高下立判。
首先因为 \(n\) 是偶数，考虑 \(\{1, 2, \dots, n - 1\} =\dfrac{n(n-1)}2 \bmod (n - 1) = 0\)， 加入 \(n\) 去掉非 1 的其他任意一个数，模 \(n - 1\) 都不是 0，因此可以 \(n\) 次询问，每次去掉 \(i\)，就可以知道 \(a_i = 1\) 还是 \(n\)，此时两个位置没有要求，然后把这两个位置删掉继续做，这时候需要检查这个位置是 \(n - i\) 还是 \(i+1\)，由于奇偶性不同可以加入 1 判断。
这样 \(n^2\) 次操作问出所有数。太劣。因为太多答案是 0。
考虑取一些互质模数，算出所有数在模这些数的余数，若 \(\prod p > 800\) 就有唯一解，可以取 \(S = 3, 5, 7, 8\)。
以 8 为例，考虑先构造一些模 8 互不相同的集合 \(S\)，对于每个数都加入这些集合询问，若为 1 就可以根据 \(S\) 的和算出当前数的和。
可以取 \(S = \{1, 2, 3, 4, n - 4, n - 3, n - 2\}\)，再依次选择一个元素 + 1，得到 7 个集合，因此需要先问出 $1, 2, 3, 4, 5, n - 4, n - 3, n - 2, n - 1, n $ 这些值的位置。牛的。
标签：do,what,分块,bmod,考虑,more,可以,equiv From： https://www.cnblogs.com/henrici3106/p/17612465.html