LCT，也就是Link-Cut Tree的缩写。它是最常见的一种解决动态树问题的工具。不过说它是树也不准确，因为它维护的可以是一片森林。
将某一个儿子的连边划分为实边，而连向其他子树的边划分为虚边。
区别在于虚实是可以动态变化的，因此要使用更高级、更灵活的Splay来维护每一条由若干实边连接而成的实链。
LCT维护的对象其实是一个森林。
1、每一个Splay维护的是一条从上到下按在原树中深度严格递增的路径，且中序遍历Splay得到的每个点的深度序列严格递增。
2、每个节点包含且仅包含于一个Splay中
3、边分为实边和虚边，实边包含在Splay中，而虚边总是由一棵Splay指向另一个节点（指向该Splay中中序遍历最靠前的点在原树中的父亲）。
Bzoj 2730
题意：给一张无向图，让你加一些出口，使得任意点删除后图上任意点都能找到出口。
复习一波点双联通分量
考虑求出割点和双联通分量，然后对于每个双联通分量，我们考虑
若这个双联通分量有两个及以上割点，那么不需要建立出口
若这个双联通分量有一个割点，那么如果这个割点删了这个图就找不到出口了，要加一个出口
若这个双联通分量没有割点，即这个子图与其他子图不连通，要加两个出口
加出口即加在任意非割点的点上即可
BZOJ 1911
题意：有$n$个数$x_i$，将其分成连续的组，每组的分为$a\sum x_i + b\sum x_i +c$，求最大的总分。
设$dp(i)$为前$i$个分组的最大的总分。设$\operatorname{sum}(n)$为$\sum\limits_{i=1}^n x_i$
则
$$
dp(i)=\max(dp(j)+a[\operatorname{sum}(i)-\operatorname{sum}(j)]^2 + b[\operatorname{sum}(i)-\operatorname{sum}(j)] + c)
$$
则决策点可以表示为点$(\operatorname{sum}(j), dp(j)+a \cdot \operatorname{sum}(j)^2 - b \cdot \operatorname{sum}(j))$
这里要维护最大值，所以与之前的斜率优化不同，维护一个上凸包即可。
注意有负数时不要用叉积，符号不能确定！
知识点
1、有负数时不要用叉积，符号不能确定
3768 简单的数学题
题意：给定$n, p$，求
$$
\sum_{i=1}^n \sum_{i=1}^n ij\gcd(i,j) \mod p
$$
枚举约数
$$
\sum_{d=1}^n d\sum_{i=1}^n \sum_{i=1}^n ij [\gcd(i,j)=d]
$$
将后面的提取因数
$$
\sum_{d=1}^n d^3 \sum_{i=1}^{\lfloor \frac nd \rfloor} \sum_{i=1}^{\lfloor \frac nd \rfloor} ij [\gcd(i,j)=1]
$$
将布尔式化成$\mu$
$$
\sum_{d=1}^n d^3 \sum_{i=1}^{\lfloor \frac nd \rfloor} \sum_{i=1}^{\lfloor \frac nd \rfloor} ij \sum_{k|i,k|j}\mu(k)
$$
先枚举$k$
$$
\sum_{d=1}^n d^3 \sum_{k=1}^{\lfloor \frac nd \rfloor} k^2 \mu(k) (\sum_{i=1}^{\lfloor \frac n{kd} \rfloor} i)^2
$$
设$T=kd$
$$
\sum_{T=1}^n (\sum_{i=1}^{\lfloor \frac nT \rfloor} i)^2 \sum_{d|T}d^3 (\frac Td)^2 \mu(\frac Td) \\
\sum_{T=1}^n (\sum_{i=1}^{\lfloor \frac nT \rfloor} i)^2 T^2\sum_{d|T}d \mu(\frac Td)
$$
后面是个卷积形式，根据$\mu * id = \varphi$
$$
\sum_{T=1}^n (\sum_{i=1}^{\lfloor \frac nT \rfloor} i)^2 T^2 \varphi(T)
$$
现在要求$T^2 \varphi(T)$的前缀和。不妨先设$g=id^2$
$$
(f * g)(i)=\sum_{d|i} d^2 \varphi(d) \times id^2(\frac id) \\
= \sum_{d|i} d^2 \varphi(d) \times (\frac id)^2 \\
= \sum_{d|i} i^2\varphi(d) \\
= i^2\sum_{d|i} \varphi(d) \\
= i^3
$$
则
$$
g(1)S(n)=\sum_{i=1}^n(f * g)(n) - \sum_{i=2}^n g(i)S(\lfloor \frac ni \rfloor) \
S(n)=\sum_{i=1}^n i^3 - \sum_{i=2}^n i^2 S(\lfloor \frac ni \rfloor)
$$
再由两个公式
$$
1^3+2^3+ \dots + n^3 = (1+2+ \dots + n)^2 \\
1^2+2^2+ \dots + n^2 = \frac{n(n+1)(2n+1)}{6}
$$
即可完成求解
坑：
1、$n$要运算时一定要先模，否则$10^{10} \times 10^{10}$马上爆炸
2、$2n$也要模
知识点：
1、整除分块只有$\lfloor \frac nd \rfloor$部分相同，可以用来乘
2、Dirichlet卷积运用
3、LCM和那题没搞明白的东西
4、预处理逆元免除$\log$
Luogu 3765
题意：维护序列的区间大于一半数的众数，带修。
第一眼以为带修主席树，感觉肯定跑不过
前置知识：Luogu 2397
求序列大于一半数的众数
本题可以采用摩尔投票法求，即将不同数两两消除，最后一定剩下的是这个众数。
这个方法必须存在大于一半数的众数
然后看这题，显然摩尔投票法是满足可加性的，那么线段树维护之。
但是如果不满足存在大于一半数的众数怎么办？
我们可以维护一个数在某个区间出现次数，这个方法是经典套路，静态则用 vector 排序后二分，而动态则需要名次树Splay维护。具体方法为在名次树上类似静态方法二分即可。
然后每次查询，更改即可。
知识点：
1、摩尔投票法
2、vector 版平衡树
Loj 2632
题意：见上。
做法($(c=容量, w=费用)$)：
将每天拆点拆成$x_i,y_i$($x$为脏餐巾点，$y$为干净餐巾点)
1、$S$到$x_i$：$(r_i, 0)$，补脏的 (用过的毛巾假设全丢掉，然后再从$S$补偿脏毛巾。以达到一个毛巾用$n$次有流量$n$)
2、$S$到$y_i$：$(∞, P)$，买入毛巾
3、$y_i$到$T$：$(r_i, 0)$，使用毛巾 (用过的毛巾假设全丢掉)
4、$x_i$到$y_{i+M}$：$(∞, F)$，快洗
5、$x_i$到$y_{i+N}$：$(∞, S)$，慢洗
6、$x_i$到$x_{i+1}$：$(∞, 0)$，存着脏毛巾
上述博客思路为：
1、先拆点，然后考虑快洗慢洗、不洗(存着脏毛巾)
2、发现错误(一个毛巾用两次只有流量$1$)，修改为舍弃流和补偿流
知识点：
1、资源调配问题，舍弃流和补偿流的方法
poj 3709
题意：给定一个数列 $a$， 分成若干段，每段至少有$k$个数， 将每段中的数减少至所有数都相同， 求最小的变化量
设$dp(i)$为前$i$个的最小变化量。
则
$$
dp(i)=\min_{i-j \leq k}(dp(j)+\operatorname{sum}(i)-\operatorname{sum}(j)-i \cdot a_{j+1} +j \cdot a_{j+1})
$$
显然可以斜率优化。决策表示为$(a_{j+1}, dp(j)-sum(j)+j \cdot a_{j+1})$，即可算斜率。
注意$i-j \leq k$的限制，我们可以考虑延迟加入决策(具体看代码)，预处理$[0,2k]$的答案。
知识点
对于这种有限制的斜率优化可以考虑延迟加入决策
Codeforces 1106E
题意：有 $k$ 个区间 $[s_j, t_j]$ 表示一段时间，每个区间有 $t_j, w_j$ 表示若选择这个区间则 $t_j$ 后才能选其他的区间，选择区间的权为 $w_j$ 。现在有一个人从 $1$ 时刻开始选区间，他会选当前能选的最大权的区间，若存在多个，选 $d_j$ 大的区间。现在有 $m$ 次机会，每次可以使得这个人在某一秒不能选区间。求当这 $m$ 次机会使用得最优时，这个人最小能选择区间权和。
正序DP不太好做。
考虑倒序DP，设$dp(i,j)$为$[i,n]$用了$j$次机会的最小权和。
则
$$
dp(i,j)=\min(dp(i+1,j-1),dp(i+1,j),dp(g, j))
$$
其中$g=\max\limits_{i \in {[s_j, t_j], j\in[1,k]}}(d_j)$
这个$g$可以用set维护。
具体就是将区间端点存起来，然后枚举时间线时看是否超出了，超出即删掉，如果有新的加入，就加入。
BZOJ 3930
题意：给定$n,K,H,L$，求
这个形式和在$[1,n],[1,m]$中的$gcd$类似，我们从$N=2$开始考虑。
显然
$$
f(k)=\sum_{d=1}^{\lfloor \frac nk \rfloor} \mu(d) \left \lfloor \frac n{kd} \right \rfloor^2
$$
扩展到高维也类似，所以可以得到
$$
f(k)= \sum_{d=1}^{\lfloor \frac Hk \rfloor} \mu(d) \left (\left \lfloor \frac H{kd} \right \rfloor - \left \lfloor \frac {L - 1}{kd} \right \rfloor \right )^n
$$
然而$\lfloor \frac Hk \rfloor$是$O(H)$级的，不能满足。
引理：
当所有数不全部相同时，$\gcd\left ( i_1, i_2, \dots, i_N \right ) \leq \max\left ( i_1, i_2, \dots, i_N \right ) - \min\left ( i_1, i_2, \dots, i_N \right )$
证明：设$d = \gcd\left ( i_1, i_2, \dots, i_N \right ), a = \min\left ( i_1, i_2, \dots, i_N \right ), b = \max\left ( i_1, i_2, \dots, i_N \right )$
显然$a = k_1d (k_1 \in \mathbb{Z}^+), b = k_2d (k_2 \in \mathbb{Z}^+, k_2 > k_1)$， 所以$b - a \geq d$，证毕。
所以$[H, L]$中的一个不全部相同的序列的$\gcd$不会超过$H - L$个，只用处理不全部相同的序列，所以可以得到
$$
f(k)= \sum_{d=1}^{\lfloor \frac Hk \rfloor - \lfloor \frac {L-1}k \rfloor} \mu(d) \left( \left (\left \lfloor \frac H{kd} \right \rfloor - \left \lfloor \frac {L - 1}{kd} \right \rfloor \right )^n - \left (\left \lfloor \frac H{kd} \right \rfloor - \left \lfloor \frac {L - 1}{kd} \right \rfloor \right )\right)+[L \leq k \leq H]
$$
注意需要加上$[L \leq k \leq H]$，因为这样就可以选$n$个$k$。
本题也可以直接杜教筛筛出$\mu(d)$的前缀和，但是我并不会……等学了杜教筛再来填坑吧。
BZOJ 2060
题意：一个初始集合($n$个元素)和一个目标集合($m$个元素)($1 \leq n,m \leq 10$)，两个操作
问对初始集合最少进行几次操作可以到达目标集合
显然最多的次数就是将初始集合全部合成一个数然后再分成目标集合，也就是次数上界为$n+m-2$
把初始集合和目标集合分成尽量多的子集让这些子集都能对应(子集元素和相等)，如果能分成$x$个子集，那么次数就是$n+m-2x$
考虑设$dp(S_1,S_2)$为把$S_1$和$S_2$最多能分成几个能相对应的子集(子集元素和相等)。则
$$
dp(S_1,S_2)=\max(dp(S_1 - k,S_2), dp(S_1,S_2 - k))
$$
若$\operatorname{sum}(S_1)=\operatorname{sum}(S_1)$，则$dp(S_1,S_2)+=1$
因为不相同时不能用上所有的，相同时加减掉一个元素一定少一个集合
知识点
1、集合DP思想
2、$\operatorname{lowbit}$来快速枚举子串，用于合并答案的递推非常好用(看代码)