Codeforces 1151E
题意：求
$$
\sum_{i=1}^n\sum_{j=i}^nf(i,j)
$$
其中$f(i,j)$表示只保留权值在$[i,j]$之间的点形成的连通块数量。

一看连通块，就考虑转化，连通块数量=点数-边数。
然后考虑每个点和每条边对答案的贡献，用点个数减掉边个数即可。

Loj 2478
题意：给定一棵 $n$ 个点的树，边权有正有负，要求在树上选出 $k+1$ 条链，使得其权值之和最大。

考虑DP。设$dp(i,j,0/1/2)$分别为$i$点子树$j$条完整链，当前 $i$ 节点的度数为 $0/1/2$ 的最大价值。度数为 $0$ 时，这个点没有链的连边。度数为 $1$ 时，这个点拖着一条未完成的链，而这条链不计入 $j$ 。度数为 $2$ 时，这个点被一条连接两个不同子树的链穿过，计入$j$。

转移见代码，状态非常经典重要。

考虑带权二分优化DP，即我们发现这个答案是关于$k, ans$的上凸函数，所以我们可以二分斜率切这个上凸函数，然后计算$k,ans$，每个物品都要减去二分的斜率值，然后直到找到极值才输出，注意上凸函数切点越左斜率越大

知识点：

agc 038C
题意：给定$n$长序列$A_i$，求
$$
\sum_{i=0}^{N-2} \sum_{j=i+1}^{N-1} \mathrm{lcm}(A_i,A_j)
$$
看起来很像莫反
我们推下式子
$$
\begin{align}
\mathrm{Ans}&=\sum_{i=1}^{N-1} \sum_{j=i+1}^{N} \mathrm{lcm}(A_i,A_j) \\
&=\sum_{i=1}^{N-1} \sum_{j=i+1}^{N} \frac{A_iA_j}{\gcd(A_i,A_j)} \\
\end{align}
$$
设$\sum\limits_{d|n} w(d)= \frac 1n$，则有
$$
\sum_{i=1}^{N-1} \sum_{j=i+1}^{N} A_iA_j \sum_{d|A_i,d|A_j} w(d) \\
$$
交换一下顺序，得
$$
\sum_{d=1}^{V} w(d) \sum_{d|A_i,d|A_j,i \leq j,i \not=j} A_iA_j \\
$$

$w$很容易算，即$w(n)=\frac 1n - \sum\limits_{d|n, d \not= n} w(d)$，调和级数筛一下即可

考虑后面的怎么计算，因为权值范围$V$比较小，我们只需要统计每个权值出现几次即可。

对每个$d$，我们统计答案，即调和级数筛一下获得$A_i$中是$d$倍数$x$的数的和，然后将和自乘就是不考虑$i \leq j,i \not=j$的答案，考虑这个的话我们就在筛的时候顺便记录$x^2$的和，减去即可，然后除以二，但是要注意有重复数字，重复数字要再多乘一个数字出现次数。

BZOJ 4197
题意：给定$n$，求出选择两个不相交集合$A,B$，不存在$d$使得$d|(x\in A), d|(y\in B)$的方案。

我们发现$n=500$以内质数小于$\sqrt n$的只有$8$个，我们考虑状压小质数当做背包容量，然后再用大质数(每个数只有最多一个)来分组做分组背包。

设$dp(S,T)$为选的集合分别是$S,T$的方案

每次大质数相同的一起转移，考虑转移时设$f(S,T,0/1)$表示大质数放$S$还是$T$的方案。

然后分别转移即可，$dp(S,T)=f(S,T,0)+f(S,T,1)-dp(S, T)$

没有大质数的可以处理完马上转移，具体看代码实现，比较简单

BZOJ 4538
题意：见上。

直接树剖剖成序列问题，然后每次修改取反修改区间即可，维护线段树的每个节点上都开个堆存最大重要值，再开一个堆代表删除节点堆，取顶时两个堆对比一下就行了。

知识点：
1、灵活运用树剖模板，线段树上维护堆

Bzoj 1132
题意：平面上有$N$个点. 求出所有以这$N$个点为顶点的三角形的面积和

已知平面3点$A,B,C$, 求三角形面积：$S=|(y_b-y_a)(x_c-x_a)-(y_c-y_a)(x_b-x_a)|$

我们可以让$A$变为坐标原点，那么$S=|y_bx_c-y_cx_b|$

那么我们可以把点按$x$坐标排序，然后枚举点$i$, 考虑$i$右边的点对答案贡献

我们发现上式像叉积并且三角形面积有向性，我们可以把右边点极角排序，然后就能确定符号了，那么直接倒序枚举$j \in (i, n]$，用个前缀和处理$k$即可

Bzoj 2115
题意：给定一张无向图带边权图，求图上一条$1 \rightarrow n$路径的异或和最大值。

路径不要求简单路径，那么这个路径就是一条链+一些环
我们随便找一条$1 \rightarrow n$的链，然后考虑在其中加上环
如果环和链有交，那么直接异或环的异或和是对的
如果没有交，我们要走过去再走回来，连接路径抵消了，也是对的

为什么我们可以随便选链呢，因为$1 \rightarrow n$的任意两条链一定可以构成环然后就是上面的问题

所以我们随便选个链，再把所有环的异或和丢进线性基

Codeforces 1059E
题意：现有$n$个点组成一棵以$1$为根的有根树，第$i$个点的点权为$w_i$,需将其分成若干条垂直路径使得每一个点当且仅当被一条垂直路径覆盖，同时，每条垂直路径长度不能超过$L$,点权和不能超过$S$，求最少需要几条垂直路径才能满足要求。特别地，无解输出$-1$。
一条垂直路径是一条不在树中弯曲的路径。
Codeforces 1039D
题意：有一棵$n$个节点的树，其中一个简单路径的集合被称为$k$合法当且仅当：树的每个节点至多属于其中一条路径，且每条路径恰好包含$k$个点对于$k∈[1,n]$，求出k合法路径集合的最多路径数即：设k合法路径集合为$S$，求最大的$|S|$
Codeforces 1042F
题意：无向无根树$n$个点，要将树叶分成集合，使得每个集合中任意两个叶子距离小于等于$k$，问能最少分成几个集合？
NOIP2018 赛道修建
题意：一颗树$n$个点，将树分成$m$条路径，使得 $m$ 条赛道中长度最小的赛道长度最大

这4题都是树上贪心的题，基本上都是树上分路径的问题。

CF1059E 直接记录每个点向上最远到哪 (因为垂直路径)，然后就子树DP，记录最长链返回父亲，最后统计条数即可

CF1039D 就直接从下往上能合并就合并，不能合并就传最长链回父亲，这是朴素做法，我们可以发现$k \leq \sqrt{n}$时直接暴力，$k \geq \sqrt{n}$时最多会有$\sqrt{n}$种答案，而且答案单调。二分就行了。

CF1042F 具体看另一博客，主要是记录最长链返回父亲

NOIP2019 就将子树所有最长链存在multiset，然后合并路径，主要是记录最长链返回父亲

所以这类问题就是一般是树上路径划分，一般用记录最长链返回和贪心合并为主。

Codeforces 446C
题意：给出一个数列，每次可以选取一个区间，按顺序加上第$i$个斐波那契数进行更新，也可以查询某一个区间的总和。

性质一

$\sum_{i=1}^n f_i = f_{n+2} - f_2$

证明即累加$f_1=f_3-f_2$

性质二

两个斐波那契数列相加仍然是斐波那契数列，只是前两项不一样，并且可以通过$f$求出这个数列，即$g_i=a \times f_{n-2} + b \times f_{n-1}$

计算方法通过累加很容易发现。

那么这里就可以线段树维护了，线段树维护每个区间的前两项和区间和，因为性质二所以区间信息可以方便pushdown

顺便提一下
pushup：显然区间和信息可合并
pushdown：性质二
query：性质二
update：性质二

Codeforces 718D
题意：给出一个$n$长序列$a_i$，维护以下操作
1、1 l r x，将$a_{i \in [l,r]}$加上$x$
2、2 l r，求$\sum\limits_{i=l}^r F(a_i)$，$F(a_i)$为斐波那契的第$x$项

斐波那契数列考虑矩阵，那么这里我们可以用线段树维护矩阵 (矩阵满足结合律，则可以轻松合并信息)

区间加一个数相当于矩阵乘多少次转移矩阵，最后答案乘上起始矩阵即可。

线段树维护$lazy$表示当前的标记 (是一个矩阵)，$sum$表示当前区间的和 (矩阵和)