Bzoj 4033
题意：有一棵点数为$N$的树，树边有边权。给你一个在$[0,N]$之内的正整数$K$，你要在这棵树中选择$K$个点，将其染成黑色，并将其他的$N-K$个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。问收益最大值是多少。

本题抛开颜色就是一个树边贡献模板题。
然后这里加入颜色的话就肯定要DP，DP方程受前面的启发设为
$dp(u,j)$为以$u$点为根子树，有$j$个黑点对答案的贡献。
然后转移就是
$$
dp(u,j)=\max(dp(u, j - k)+dp(v, k)+val \times w)
$$

其中$w$为贡献，$val$为
$$
val=k \cdot (m - k) + (siz(v)-k) \cdot (n - m - (sz(v) - k))
$$

即考虑边$(u, v)$的贡献，左边有几个黑点，右边有几个白点，同色点相乘，异色点相加即可。

然后注意细节，$dp$初始化为$-∞$，然后要判
if (dp[u][j - k] >= 0)

并且每个循环的上界都要加上$siz$的限制，以确保复杂度大概为$O(n^2)$

for (int j = min(siz[u], m); j >= 0; --j)
for (int k = 0; k <= min(siz[e.v], j); ++k)

Codeforces 1099F
题意：一棵 $n$ 个节点，以 $1$ 为根的带边权树，每个点包含 $x_i$ 个曲奇， 需要 $t_i$ 的时间吃掉一块曲奇。有两个人Mitya和Vasya在轮流玩游戏，Mitya先手。在根处有一个小动物，Mitya每次可以选择花费边权$l_i$的时间来到达当前点的孩子节点或者直接结束游戏，从这里返回选择性吃一些曲奇。Vasya 切断当前节点到一个儿子的连接(可以不一定要切)。整个游戏限时为 $T$
求最坏情况下能吃到的曲奇个数。

这题比较麻烦……可以发现我们不用模拟整个过程，直接在往下的过程中路程乘二，然后直接吃曲奇即可。而且我们尽量要在花费最小的位置吃曲奇。那么当前节点位置到根上的曲奇都可以作为候选。那么我们可以用数据结构维护曲奇。

我们先忽略掉 Vasya，即不考虑断边的情况，设$f(u)$为根到$u$的不考虑断边下的最优解。
我们要尽量多吃曲奇，那么我们尽量要在花费最小的位置吃曲奇，所以我们不妨维护一个值域在$t$上的一个树状数组，记录值为$t_i \cdot x_i$，这个树状数组上的前缀和即为最优吃曲奇的时间，我们在树状数组上二分找到一个位置使得其是$\leq T - 2 \cdot S$的最大值，其中$S$为从根到该位置的路径长度。这样找到的一定是最优的。因为值域从$1,2,3,\cdots,maxt$排序。为了统计到底有多少个曲奇能吃，那么再开一个值域在$t$上的一个树状数组，记录值为$x_i$，那么前缀和就是有多少个曲奇。最后还需要补不足够部分的曲奇，具体看代码实现，小技巧是有余数要补的可以方便化直接减一，这样整除就不用讨论。

然后考虑 Vasya，Vasya 一定断开获益最大的一条边，所以 Mitya 只能取到次优值。
设$dp(u)$为$u$为子树，考虑断边的最优值，$maxd(u), cid(u)$分别为$u$为子树不包括$u$，考虑断边的最优值的次优值。
如果当前是根，那么$dp(1)=max(f(1), maxd(1))$，因为 Mitya 先手
否则只能取到次大值，则$dp(u)=max(f(u), cid(u))$
$maxd(u)$和$cid(u)$用次大值的更新方法来更新即可。用子树的$dp$值来更新。

真是一个数据结构+DP好题。。

$$
{\color{red}{211}}/350
$$

1、CF 1009F (树上启发式合并)
2、Bzoj 2154 (莫比乌斯反演)
3、Bzoj 3124 (树的直径)
4、CF 1108 E1 (枚举)
5、Bzoj 3994 (莫比乌斯反演)
6、Bzoj 1233 (DP+单调队列+结论)
7、CF 1107 ABC
8、Bzoj 1832/Bzoj 1787 (倍增LCA)
9、Bzoj 1858 (线段树维护01序列翻转最大字段和)
10、Bzoj 2005 (莫比乌斯反演)
11、CF 984 ABC
12、Poj 2374 (线段树)
13、Bzoj 1718 (桥+贪心)
14、Bzoj 3529 (莫比乌斯反演+离线+树状数组)
15、DG联考
16、CF 975 ABC
17、CF 311B (DP，二维斜率优化)
18、Bzoj 3930 (莫比乌斯反演 + GCD性质 / 杜教筛)
19、《差分与前缀和》 by ruanxingzhi
20、Bzoj 1385 (规律，GCD)
21、Bzoj 2064 (集合DP)
22、DG联考
23、Bzoj 3033 (欧拉回路+DFS)
24、Dirichlet 卷积
25、CF 1109 ACD
26、CF 1106 (倒序DP，set)
27、Bzoj 1497 (最大权闭合子图，最小割)
28、Loj 6008 「网络流 24 题」餐巾计划 (最小费用最大流，资源调配)
29、Poj 3709 (斜率优化DP，延迟加入决策)
30、杜教筛模板
31、dfs序七个经典问题 in 《数据结构漫谈》 by ruanxingzhi
32、Luogu 3768 简单的数学题 (莫比乌斯反演)
33、Bzoj 1911 (最大化斜率优化)
34、Bzoj 1012 (树状数组最大值)
35、Bzoj 2730 (双联通分量+分类讨论)
36、Bzoj 1925 (组合数DP，波动序列性质)
37、CF 1111 ABC
38、LCT 模板
39、Hdu 5608 (莫比乌斯反演，杜教筛)
40、CF 1110 ABCE
41、CF 1110 D
42、Bzoj 3126 (DP+单调队列/差分约束)
43、Bzoj 1047 (单调队列)
44、Bzoj 1226 (状压DP)
45、CF 1104D (交互，二分，倍增)
46、Bzoj 1861 (Splay)
47、Bzoj 1058 (Set)
48、Bzoj 1801 (DP)
49、CF 1114 ABC
50、CF 1114 D (区间DP) $\color{green}(\text{Finished on Feb. 10th, 2019})$

poj 2135
题意：一个无向图，起点终点固定，来回一次，不重复任何一条道路，求最小道路数(就是路径长度)

这种最短路没法解决的可以想想网络流，因为网络流的最小费用和最短路有相似点，而可以通过容量等方式限制最短路的形式。

设一个超级源和一个超级汇，超级源连$1$点边$(cap=2, w=0)$, $n$点连超级汇边$(cap=2, w=0)$
然后对于图中的一条边$(x,y)$，连边$(cap=1,w=v_{x,y})$
这个容量就是限制路径条数的，相当于走了一次以后即割断不能再走，而连接超级源汇的边容量为$2$，为的是找到两条路径。

Loj 2632
题意：见上。

类似Poj 3422，本题也是利用拆边技巧。对于几个源和几个汇，建超级源 / 超级汇连边最大费用最大流即可。

知识点：
1、拆边技巧

Codeforces 817F
题意：对一个维护三种操作：
1 将$[l,r]$中的数全部加入集合中。
2 将集合中$[l,r]$范围内的数删去。
3 将集合中在$[l,r]$中的数删去，并将之前不在集合中的数加入集合

考虑将每个数字当前一个位置，$0$表示有，$1$表示没有，然后$mex$就是最前面的$0$。显然可以二分。

数据大，考虑离散化。对于1操作，则是区间修改为$1$。对于$2$操作，则是区间修改为$0$
若没有第三个操作，我们完全可以用树状数组+二分完成。而这里可以用线段树代替。

区间翻转相当于$sum=(r-l+1)-sum$
线段树维护两个标记即可。注意标记的抵消的写法。具体看代码。

BZOJ 4004
题意：给你$n$个$m$维向量，每个向量有一个权值，求最小权极大线性无关组。

直接将其看作一个矩阵高斯消元，然后解出来的简化阶梯矩阵所有非零向量线性无关，称为秩。

对答案统计直接在消元过程中统计。

这题也让我知道高斯消元最后矩阵如果有一行有多个元素大于$0$意思是因为其他元没消掉这一位的数，并不是无解。

注意本题卡精度，可以开 long double

Luogu 1084
题意：见上。

可以发现答案具有二分性质，所以我们二分一个答案$mid$来判断。
只要保证每个移动长度不超过$mid$即可。
那么我们可以将一些不能到达根子节点的军队直接能爬上来多少就爬上来多少，在爬上来的位置标记，不能爬到根。
爬完之后，对树进行一次 DFS，更新根节点子节点下的子树是否全部被封锁。
然后将其他军队爬到根节点的子节点，这些军队分成两种：
第一种是剩余距离不足以经过根再回去原来的位置的军队
第二种是除了这些的其他军队

对于第一种军队所在的位置，一定是这个子树中的军队占领。
因为如果是其他子树的军队来占领，不那么优，因为第一种军队去占领其他子树的军队，那个占领这个位置的军队绝对可以占领那个位置，证毕。

所以我们可以留下一个剩余距离最小的第一种军队来占领这颗子树，然后其他军队通过贪心的方法，用剩余距离尽量小的军队取占领距离小的位置。

注意 $chk$ 实现，找了一年BUG…

poj 3422
题意：给定 $n^2$的矩阵，含有元素值，每次从最左上角开始出发，每次向右或者向下一格。终点是右下角, 每经过一个格子，获取它的值，并把该格子的值变成$0$.问经过$k$次从左上角到右下角。能得到的数值和最大多少。

把走几次看成容量，数值和看出权值。$(w=w_0,cap=c_0)$表示权值$w_0$, 容量$c_0$
本题如果格子值不会变，那么直接点转边，入点到出点连边$(w=a_{i,j},cap=k)$，然后在网格图中连边$(w=0,cap=k)$，然后求最大费用最大流。

但是这里格子值会变化，所以我们要限制多次走这个点获得多次收益的情况。
我们将入点到出点的边拆边，拆成$(w=a_{i,j}, cap=1), (w=0, cap=k-1)$两条边，然后这样做就可以解决问题了，由于最大费用基于最大流，所以一定能完成不超过$k$次(全部数取完后也可以随便选择路径走，等效)。

BZOJ 1791
题意：求基环森林中的每棵基环树的直径之和。

可以对每个基环树进行求解，显然答案为每个基环树直径的和。
考虑怎么求基环树的直径。
我们可以将环找出来，然后当成一个广义根，对环上每个点向下做树直径DP，然后问题转化为在一个环上选取两个数使得
$$
a(x)+a(y)+\max(|dis_x-dis_y|, dis_n - |dis_x-dis_y|)
$$
其中$dis_i$为从环上某个点某个方向出发到$i$的距离，$a$为每个点向下做的树直径长度。
注意到这个式子和CH 5501的式子类似，所以可以单调队列维护。具体方法和那题差不多。

找环的方法为dfs，同时记录时间戳，将当前搜索链(当前点到最祖先的节点的链)上的的加入到栈，若出现一条反向边，则一定存在一个环，并且这条边是环上的边，所以一直退栈直到取出反向边所指的节点。这些节点就是环上的点。但是注意了提前退出要把所有标记都标记好，否则有错解。

注意环上一个点有几个分支的情况，这必须在处理树直径时加上ans = max(ans, d[u] + d[e.v] + e.w)
单调队列中如果没有元素，则不能直接转移，只能更新为他的$a$值