1.CF1976F Remove Bridges
树的根度数为 \(1\)，先开始树上每条边都是割边，连接根和叶子可以去掉更多的割边，先连接一个叶子和根，然后另外的叶子两两组合，每次肯定删去更多的点，删去一部分点后有些删去的就会减少，想到长链剖分，第一次选最大的，后面每次选两个最大的即可。
2.ABC374G Only One Product Name
如果 \(S_j\) 能接在 \(S_i\) 后面，那么 \(i\rightarrow j\)，建完这个图，发现有环，环显然是可以缩成一个点的，问题就转化成了 DAG 的最小路径覆盖（可交）。先算不可交的，将每个点拆成入点和出点，如果 \(u,v\) 有边，那么从 \(u\) 的入点连向 \(v\) 的出点，那么入点出点天然的构成了一个二分图，假定先开始有 \(n\) 条路径，那么在二分图上连接一条边，等价于原图减少了一条路径，二分图最大匹配时覆盖路径最小，问题转化为二分图最大匹配。然后处理可交的问题，用传递闭包处理一下，算一下哪些点能到达，然后就跟上面一样。
3.CF1895F Fancy Arrays
容斥用 \(\min a_i\le x+k-1\) 的方案数减去 \(\max a_i<x\) 的方案数，第一个用最小值和差分数组算，最小值有 \(x+k\) 种，由于差分数组天然决定了数组的大小关系，所以差分数组的方案数为 \((2\times k+1)^{n-1}\)，乘法原理相乘即可。第二种情况由于 \(x\) 很小可以直接暴力 dp，但是 \(n\) 太大所以要用矩阵优化。贡献 \(1\) 减去贡献 \(2\) 即为答案。
4.CF1860F Evaluate RBS
\((x,y)\) 是一个二元不好处理，考虑消元：\(ax+by=y(a\times \frac{x}{y}+b)\)，全部同时除以 \(y\)，那么 \(a\) 即为 \(k\),\(b\) 即为 \(b\)，\(\frac{x}{y}\) 即为自变量，由此转化为一元关系，并且将每个元组变成了直线，\(n\) 条直线产生 \(n^2\) 个交点，将这些交点记录下来，并按照从大到小排序，会发现自变量在交点左侧，交点上以及右侧都能确定两条直线的 \(y\) 大小，也即顺序，所以从左到右移动交点，并且维护直线的 rank，括号匹配的充要条件是前缀最小值大于等于 \(0\)，且和为 \(0\)，用线段树维护前缀和即可。
5.CF1849F XOR Partition
每次找到全局最小异或对，将它们连边，表示它们不能在同一个部分，一棵树天然决定了一个集合的划分，所以问题转化为求异或的 MST，这个就是板子了：有一个叫 Boruvka 的算法就是用来解决完全图的生成树问题，算法大致就是把所有点当成一个连通块，然后每个连通块找到外部最小的边，然后连上，问题在于如何找到外部最小的边，即求最小异或值，直接使用 0/1 trie 即可。最后得到了树黑白染色即可。
6.CF1841F Monocarp and a Strategic Game
答案具有单调性可以二分，假定现在 check \(p\)，枚举题中所给的左右分界处，问题就变成了左右选最多的数满足和 \(\le p\) 并且和 \(\ge k\)，本来我是用主席树实现的，复杂度为 \(\mathcal{O}(b\log^2 V)\)，被卡常了过不了，所以改成了堆。
7.CF1814F Communication Towers
看到时间一眼线段树分治，但是这个是点，不是板子，一个小技巧把它变成加边，每条边加入的时候看它的两个点交集的事件，但是这个我竟然没想到。然后就是正常的线段树分治，难点在于可撤销并查集的处理。正常操作的并查集后，在每个时间节点也就是叶子，对 \(1\) 所在的连通块标价 \(+1\)，然后在进行并查集回退的时候子节点加上原来的贡献，不过为了避免前面有些本来有标记，所以合并的时候提前减一下，这样就可以保证增量是对的了。
标签：二分,10,路径,最小,然后,入点,交点,杂题 From： https://www.cnblogs.com/BigJoker/p/18462445