Codeforces 609E
题意：询问一个图包含某条边的最小生成树。对每条边进行询问。

先求出最小生成树，然后对于在最小生成树的边直接输出最小生成树的最优值，否则，考虑将这条边$(u, v)$加入最小生成树，则必然会产生环，其中环为最小生成树上$u$到$v$以及边$(u, v)$，我们要在$u$到$v$找权最大的边删除。使用倍增就能够完成。用 LCA 爬即可。

本题思路与次小生成树思路类似。

Codeforces 907E
题意：给一个连通有向图，每次选出一个点，这个点所连的所有点就可以成为一个团(完全图，即每两个顶点直接有一条边)，求最少选几个点使得整个图成为一个团，输出方案。

题目数据范围提示是状压DP或者搜索。这里明显是状压DP。
设$dp(S)$为当前团的节点状态，$st_i$为这个点连通点的状态，则
$$dp(S|st_i)=min(dp(s)+1)$$
输出方案，如果当前DP更新了，就把前驱记录，然后最后输出即可。

如果原图已经是团，则直接输出0

知识点：
数据范围小：状压、暴力DFS
团=完全图，即每两个顶点直接有一条边

Codeforces 570D
题意：一棵树根为1，告诉你每个点上的字母。问$v$节点子树（包括$v$节点）在第$h$行的所有节点的字母能否组成回文串。

为什么这题卡常啊……
子树问题考虑 DFS 序，这里因为和深度有关就分层处理。每一层建 vector 存这层每个字母在 DFS 序中的位置，因为按照 DFS 序存，vector 内部有序，所以每次查询在 vector 二分一个子树区间统计个数，能否组成回文当且仅当出现奇数次字母小于等于1

Codeforces 686D
题意：给一棵树求每个子树的重心。

几个定理：

1把两个树通过一条边相连得到一个新的树，那么新的树的重心在连接原来两个树的重心的路径上。
2把一个树添加或删除一个叶子，那么它的重心最多只移动一条边的距离
3去掉任意一个重心后，生成的各个块的节点数的最大值一定小于等于原树的节点数除以2。
4以一棵树的重心为根的子树的节点个数，一定大于等于该树节点总数的一半。
5在一棵树的所有子树中，找到某一子树，使得其节点数恰好大于等于原树节点总数一半，那么该子树的根一定是一个重心。(如果该节点不是重心，也就是把它去掉后产生的连通块中至少有一个节点个数大于原树节点个数的一半。)

这里用定理1、3

对于当前一个子树求重心，他的重心在他的最大子树的重心和子树的根的路径上(定理1)。所以 DFS 即可。
判断路径上是否是重心：判断整个子树在当前枚举位置断开，生成的两个块的节点数的最大值是否小于等于原树的节点数除以2(定理3)

Codeforces 701E
题意：有$n$个城市，有$2k$个学校在城市中，要对这$2k$个学校进行连边，使得所有连出来的边的和最大，每条边边权为$1$

考虑每条边对答案的贡献。对于一条边，因为要最大化和，所以他左边的学校一定要连到右边的学校，所以每条边的贡献是$min(left, right)$，$left$是左边的学校个数，$right=2k-left$。DFS 处理即可，随意定一个根都行。

知识点：对于这种路径覆盖，树上计数的题目，多想想边点对答案的贡献。

Codeforces 796D
题意：有一些特殊点，要求所有点距离特殊点的距离不能超过$k$，问你最多能去掉几条边。

考虑多源 BFS ，将每个特殊点初始加入 BFS 队列。由于 BFS 特殊性质，步长为1的 BFS 找到的都是最短路径。所以每个点第一次被找到都是离特殊点的最短距离。所以如果当前一条边，点已经被访问，且这条边还没被访问，这条边可以被删除。

知识点：
这道题的多源 BFS思路类似CF 987D，都是多源然后找其他点。并且这道题不仅仅可以对点进行标记，也可以对边进行标记，与欧拉回路的寻找类似。
DFS 和 BFS 慎重选择，步长为1的 BFS 有最短路的特性

Codeforces 987F
题意：给定一个大小为$m$的集合，每一个数都在$[0 ,2^n−1]$，如果两个数$x,y$满足x&y=0就连一条无向边，问这$m$个数连成的图有多少个连通分量。

对于一个数，它$n​$位取反的二进制数上删除一些1都可以和这个数连边。所以我们就 DFS 枚举每个数取反之后删掉哪些1，如果又找到另一个集合中的数就做一样的操作。一次 DFS 就相当于找一个连通分量。

知识点：二进制问题，可以取反等操作来简化问题，并且连通分量可以用 DFS 进行求解。

Codeforces 987D
题意：给你$n$个点$m$条边，$k$种货物，和一个$s$，之后让你从每个点开始走，收集到$s$种货物的最短路径长度。

因为$k$小只有$100$，所以我们直接把货物种类相同的用一个 vector 存起来，然后每次 BFS 每一种货物找他们到每个点的最短距离。每个点存每种货物到这个点的最短距离。之后询问排序这些距离取最小的$s$个即可。

知识点：数据小，就可以对着这个东西乱搞(暴力啊，存下来开桶什么的)

Codeforces 1003E
题意：要构造一棵$n$个点的直径为$d$，并且每个点度数必须小于等于$k$的树

先将直径连起来，然后从中间开始在直径上拓展树，子树上每个点到直径两端都不可以超过$d$，并且要满足每个点度数必须小于等于$k$。用 DFS 完成拓展子树。算是一个细节题，注意处处当前节点如果达到$n$就马上退出

模板及讲解

斜率优化解决什么问题

DP方程形如$dp(i)=\min(dp(j)+(a_i-a_j)^2)$，有像$(a_i-a_j)^2$这样与$i, j$都相关的信息，就不能用单调队列等来优化，要利用斜率优化来做。

斜率优化

例题：Bzoj 1010

有$n$个数${C_n}$，分成连续的若干段，每段（假设从第$j$个到第$i$个组成一段）的分数为$(X-L)^2$，$X$为$j-i+ \sum C_k , i \leq k \leq j$，其中$L$是一个常量。目标：各段分数的总和最小。

设$dp(i)$表示分组完前$i$件物品的最小花费, $sum_i$表示是前$i$件物品的长度和。
$dp(i)=\min(dp(j)+(sum_i-sum_j+i-j-L-1)^2|1 \leq j < i)$
设$S_i=sum_i+i$，则$dp(i)=\min(dp(j)+(S_i-S_j-L-1)^2)$
设$P=L+1​$, 代入，$dp(i)=dp(j)+(S_i-S_j-P)^2$

证明决策单调性

使用数学归纳法证明。
假设$i$前有两个决策$j, k(j < k)$, 且决策$k$比$j$优，则
$$dp(j)+(S_i-S_j-P)^2 > dp(k)+(S_i-S_k-P)^2 –(1)$$
假设$i$后面的某状态$t$有$S(t)=S(i)+v$，则
$$dp(j)+(S_t-S_j-P)^2 > dp(k)+(S_t-S_k-P)^2$$
$$dp(j)+(S_i-S_j-P)^2 +2v(S_i-S_j-P) + v^2 > dp(k)+(S_i-S_k-P)^2 +2v(S_i-S_k-P) + v^2$$
因为$S_i-S_j > S_i-S_k$并且$P \in \mathbb N+$，所以$S_i-S_j-P > S_i-S_k-P$，综合(1)，假设(1)成立

用点来求斜率即可。

斜率斜截式

将常数、仅和$i$相关的项、仅与$j$相关的项、$i、j$乘积项分开

分解，$dp(i)=dp(j)+S_i^2-2S_i \cdot (S_j + P) + (S_j+P)^2$
移项，$2S_i \cdot (S_j+P)+dp(i)=dp(j)+S_i^2+(S_j+P)^2$
$dp(j)+(S_j+P)^2+S_i^2=dp(i)+2S_i(S_j+P)$
把左边($dp(j)+(S_j+P)^2+S_i^2$)看成平面直角坐标系的$y$坐标，右边的$2(S_j+P)$看成$x$坐标。
那么这就是一条$k=S_i, b=dp(i)$的直线方程。决策$j$可以表示为坐标$(2(S_j+P), dp(j)+S_i^2+(S_j+P)^2)$
这里每一条直线的$x$都单调递增，$k$也单调递增。且对于同一个$i$，$k$为定值，所以我们对于每个$i$转移时只需要在知道斜率的情况下将截距$b=dp(i)$最小化。

决策的舍弃 (l)

那么现在问题转化为斜率为$S_i$的直线过一个决策$j$($j$点)，求出截距最小的那一条直线。
那么如果过了$j$点就代表从$j$状态转移到$i$。现在有以下情况：

$k_{AB}$的斜率比直线斜率$S_i$小，那么就要舍弃$A$点。后面点更优，因为

直线过$A$点时

直线过$B$点时

比较

显然在$B$点截距$dp(i)$更小，比$A$点更优，并且直线斜率单增，以后所有的斜率都不会从$j$转移。