#293 P6822
题目传送门
图论题考虑建模。拆点，对于一个点，将其拆为“以它为一端的边权种类个数”个点，然后相邻点连边，小往大补权值，大往小零边权即可。
时间复杂度 \(O(m\log m)\)。
#294 P11815
题目传送门
调整法证明贪心。
性质零：要尽可能多的把动物放在一个点。
证明：\(\dfrac{(x+1)x}{2}\) 是上凸的。
性质一：至多选取两个角。
证明：考虑一个不能放点的矩阵一定会至少保留大矩阵的两个角。如果选取了多于 \(3\) 个角，那么固定选择了最多元素的角，那么肯定存在一种策略使得可以通过调整每一种动物选择的位置来使得最后只剩 \(2\) 个角上有动物，并且权值更优。
性质二：至多选择一个非角点。
证明：考虑如果选择了多个非角点，那么保留动物数最多的点，将其他非角点上的动物放到任意一个角上，接下来按性质一证明中的方法进行调整可以得到更优方案。
那么不妨钦定选择哪两个角是可能有动物的，然后枚举非角点，但是这样会很麻烦。考虑只钦定一个角点，然后枚举非角点，将可以放的放完后就可以认为剩下的都放在一个角，由性质一证明可以保证其正确性。
时间复杂度 \(O(n+XY)\)。
#295 P6351
题目传送门
首先，题目就是在求 \(u\) 和 \(v\) 是否在同一个边双。那么考虑记一条边的边权为它被删除的时间（没有被删除就记为 \(q+1\)），那么跑一颗最大权生成树，然后就是判断一对点的路径是否被非树边覆盖。
这里用 LCA 和并查集实现是 \(O(n\log n)\)，用 dfn 序的性质和边权特殊性可以去掉排序和 LCA，实现出 \(O(n)\) 的算法。
#296 P11095
题目传送门
首先，对两个元素都有限制，直接求答案是困难的，考虑固定一部分然后最小化另一部分，于是我们枚举最大边权 \(X\)，然后将所有边权不超过 \(X\) 的边加入，将边双缩点，称一个边双的最小权为边双内部的最小边权，于是一个点可以经过的最小边为它所在边双到 \(1\) 所在边双的路径上的最小最小权。这样就得到 \(O(n^2)\) 做法。
考虑枚举最大值每次都重新跑一次边双其实是很不优的，考虑加边对边双的影响：不妨先构建出原图的最小生成树，那么如果加树边，那么不会增加边双；如果加非树边，那么才会构成边双。于是考虑根据加边类型进行分讨；
- 如果加树边，且加了之后才和 \(1\) 连通：在连通性上把两个块合并，然后在深度最小的点处对子树进行 ckmn，并将块内的答案清零。（因为之前的答案是无效的）
- 如果加树边，且加了之后没有和 \(1\) 连通：在连通性上把两个块合并。
- 如果加非树边：那么直接缩点，然后在子树处进行 ckmn。
时间复杂度均摊 \(O((n+m)\log n)\)，
#297 P5953
题目传送门
很劣的均摊 \(O(nm\log nm)\) 做法。
对每一种颜色分开考虑。对于位于 \((x,y)\) 的颜色，它可以贡献的矩形左下角的横坐标位于 \([x,x+k)\)，右下角位于 \([y,y+k)\)。一个颜色可以贡献的所有区间就是这些矩形的矩形并。
因为要求最大值，所以考虑要维护这个矩形覆盖了哪些位置。开一颗线段树维护区间被覆盖次数，拆矩形，做扫描线，修改时如果区间有 \(1\) 变 \(0\) 或 \(0\) 变 \(1\)，那么就搜索到满足整个区间都发生这样的变化。因为 \(0\) 变 \(1\) 和 \(1\) 变 \(0\) 至多发生 \(O(nm)\) 次，所以均摊 \(O(nm\log nm)\)。
#298 P8171
题目传送门
考虑全局询问怎么做。对于每一种颜色，记其第 \(i\) 次出现位置为 \(p_i\)，特别的，在 \(0\) 和 \(n+1\) 上认为每一种颜色都出现了。 令 \(f(i)=\dfrac{i(i+1)}{2}\)，那么答案可以表示为 \(f(n)-\sum_{i=1}f(p_i-p_{i-1})\) 因为 \(f(i)\) 是上凸的，所以由调整法可以得知当 \(p_i\) 放在一起（形成一个同色连续段）时，该颜色的贡献最小。
数学直觉告诉我们：将所有颜色按出现次数从小到大，轮流放在数组的左右两侧，此时得到的序列答案最小。考虑证明该结论，不妨令排序后的第 \(i\) 种颜色出现了 \(t_i\) 次。
考虑对于两个颜色 \(i\) 和 \(j\) 满足 \(i<j\)，且两个颜色左侧有 \(L\) 个位置已经被占。如果 \(j\) 放在 \(i\) 右侧、左侧时，那么 \(i,j\) 的贡献和分别为
上式减下式，得到：
因此让 \(i\) 放 \(j\) 左侧不会更劣。因为 \(f(i)\) 是上凸的，所以 \(i\) 会选择左右两侧中 \(L\) 较小的一边放。因为 \(t_i\) 递增，所以轮流放总是可以选到较小的一边。
考虑怎么做区间询问。注意到 \(q\) 和 \(n\) 的上界存在较大差异，且时限对树形数据结构较为宽松，不妨考虑莫队。令块长为 \(\dfrac{n}{\sqrt q}\)，可以做到 \(O(n\sqrt q)\) 次移动和 \(O(q)\) 次询问答案。一个广为人知的结论是任意正整数 \(n\) 最多可以表示为 \(O(\sqrt n)\) 个不同正整数的和，于是注意到只有 \(O(\sqrt n)\) 个不同的出现次数。
考虑对于一类出现次数怎么快速算。记 \(l_i\) 表示 \(i\) 颜色放置时的 \(L\)，\(t\) 为当前讨论的出现次数，\(x\) 表示有 \(x\) 中颜色出现次数为 \(t\)。那么由上述过程可以得出 \(l_i=l_{i-2}+t_{i-2}\)，启发我们对编号的奇偶性分类讨论。令当前出现次数编号最小的颜色为 \(i\)，做补集转化，求它不能做出贡献的区间数量，那么这个值为 \(f(l_i)+f(n-l_i-t)\)。 \(i+2\) 的值是 \(f(l_i+t)+f(n-l_i-2t)\)。考虑递推这个值，不妨先研究以下式子的值：
那么将真实数值带入得到：
那么只需要求 \(\sum k\) 和 \(\sum k^2\) 即可，这两个式子都有 \(O(1)\) 求前缀和的方法。
于是时间复杂度就是 \(O(q\sqrt n)\)。
当然，要做到这个复杂度，需要注意找那 \(O(\sqrt n)\) 个出现次数时，需要用一些 \(O(1)\) 的维护方法，比如基数排序。
参考代码是 \(O(q\sqrt n\log n)\) 的，块长经过微调。
#299 P11606
题目传送门
考虑怎么找根。一个点是根的充分条件是：
- 它没有被钦定祖先；
- 它没有被钦定不是一个节点的祖先。
如果有多个满足该条件的点，任选一个即可。
接下来就考虑构造不是根的点了。但是我们也注意到它虽然不是这棵树的根，但是也是它子树的根。于是我们用并查集维护形如若 \(x\) 挂在 \(u\) 子树上，则 \(y\) 必须挂在 \(u\) 上的点对关系 \(x,y\)。然后再根据这些关系来维护一个点能否成为子树根。
还剩一个问题：一个点能挂就挂一定是最优的吗？答案是是的。因为它越早挂就越早可以刻画不是节点祖先的限制。
时间复杂度 \(O(nm)\)。
#300 P11927
题目传送门
注意到权值之间是乘积贡献，那么考虑做法应该与值域相关。\(O(nV)\) 的做法是比较容易想到的，但是不能接受，考虑 meet in middle。
记 \(f_{i,j}\) 表示从 \(1\) 到 \(i\) 且权值积为 \(j\) 是否可行，\(g_{i,j}\) 表示从 \(i\) 到 \(n\) 且权值积为 \(j\) 的最大可接受的权值积。有结论一条路径总可以找到一条边，使得路径前一段和后一段权值积均不超过 \(\sqrt V\)。这个证明考虑找一条边使得前一段权值积大于 \(\sqrt V\) 且权值最小，找一条边使得后一段权值积大于 \(\sqrt V\) 且权值最小，因为没有符合上述条件的边，所以这两条边在路径中应该是相邻的，那么以这两条边为界，将前一半和后一半的权值积与这两条边的权值相乘，那么答案一定大于 \(V\)。因此枚举边即可。
求 \(g_{i,j}\) 时要注意转移的顺序，需要采取类似 Dijkstra 的方法来转移。
时间复杂度 \(O(n\sqrt V\log m)\)。