题解假设最小生成树$T$和$T’$按照权重排序后的边为$(e_0,e_1,…)$和$(e_0’, e_1’,…)$, 引入记号$E_i$和$E_i’$，分别为$T$和$T’$的第$0$到第$i$条边的集合 假设$e_k$和$e_k’$为第一对不是同一条边的位置，假设$e_k$为边$(u, v)$, $e_k’$为$(u’, v’)$，且此时$(u,v)$不在$T’$中 证明第一部分： 在$T’$中必然有一条$u->v$的路径，记为$P’(u,v)$： $P’(u,v)$不可能只包含$E ...

题解给定一个序列，要求实现区间取$min$（即区间内$a_i$更新为$min(a_i,val)$），区间求$max$，区间求$sum$。 做法： 维护区间最大值$mx$，区间严格次大值$sx$，区间最大值出现的次数$cx$，然后进行分类讨论： 　　1、$val>=mx$，明显对区间无影响，退出； 　　2、$sx<val<mx$，此时$mx$会被更改成$val$，而$sx,cx$则不变，对区间和$sum$的贡献为$(mx-val)*cx$；（此处不能使$sx=val$，否则在更新 ...

题解问题为求$\sum_{i=L}^R f(i \oplus x)^2$ 先将区间分成两个前缀的差，现在只需要考虑$[0,R] \oplus x$ 从高到低枚举最高位$w$ 设$x’$表示$x$去掉第$w$位的值 设$x^w$表示只保留$x$的$[0,w-1]$位的值 如果$R<2^w$，递归到更小的$w$进行处理 如过$R\geq 2^w$，那么可以考虑$[0,R]=[0,2^w-1]+[2^w,R]$ $[0,2^w-1]\oplus x$ $=[0,2^w-1] \oplus x^w ...

关于线性基比较经典的四道题目。

关于AC自动机比较经典的九道题目。

回文树能够以O(n)的时间求出字符串中本质不同的回文串个数（最多为n个，证明考虑每次插入一个新的后缀，如果形成的新的最长回文串不是整个串，则一定在前面插入时出现过）和其长度与出现次数。

虚树可以用来解决在树上的多次询问，约束总询问点数的动态规划问题，相较直接BFS的高复杂度，虚树可以将开销降到与单次询问点数相关的时间复杂度之内。

二分答案+差分约束系统。

通过树分治优化动态规划方程。

DP预处理+大搜索题。