Codeforces 544D
题意：给出$n$个点，$m$条边权为$1$的无向边，破坏最多的道路，使得从$s_1$到$t_1,s_2$到$t_2$的距离不超过$l_1,l_2$
对于$s_1$到$t_1$，最优肯定取最短路，2同理。
但是这两条路径可能重复更优，也就是说1取最短路而2可以在$l$范围之内不取最短路而使用1的某些边来减少边数的增加
所以我们枚举路径$(i,j)$，取每个起点终点经过这条路径的长度最短的。4种情况。最后取反答案即可。记得可能两条路径没有重合部分，直接赋值$dis(s_1,t_1)+dis(s_2,t_2)$
知识点：本题与CF 954D类似，都是求完最短路之后枚举边/路径来算答案。
对于权为$1$的图，可以用 BFS $O(n^2)$求多源最短路。而不是用Floyd $O(n^3)$的算法(或者$O(n(n+m)logn)=O(n^2+mnlogn)$)
本题将删除化为选择。
Codeforces 489D
题意：给出$n$点，$m$条有向边，问有多少个如下图的菱形
一个菱形有两条路径组成，如果我们找到$u$到$v$的不同路径数量，就可以用$C_n^2$来计算有几个菱形了。枚举这样的三元组来找路径
Codeforces 500D
题意：给一棵有$n$个节点的树，有$q$次操作，每次操作将改变某条边边权，问改变后，从$n$个点中等概率任取三点，将这三点用最短路连接起来的距离和$d(a,b)+d(a,c)+d(b,c)$的数学期望值。
树上计数一般这种整棵树计数的就是边点贡献。这里明显边贡献。算出每条边每次要计算几次即可。因为维修道路并不会影响这些次数。
对于一条边，他左边有$x$个点，右边则有$n-x$个点，记为$y$。那么通过这条边的方案数(左边选2个，右边选1个或者反之)为$yC^2_x+xC^2_y$，化简后得$(n-x)(n-2)x$，就可以这样每个点计算然后除以$C_n^3$即可。或者直接除，化简得$\frac{6(n-x)x}{n(n-1)}$，然后只要每个点记录$6(n-x)x$，然后询问时除以$n(n-1)$即可。
知识点：树上整棵数计数/最优值等路径覆盖问题和边贡献有关。本题与CF 701思想类似。
Codeforces 545E
题意：给定一个无向图和一个点$u$，找出若干条边组成一个子树，要求这个子树中$u$到其他个点的最短距离与在原图中的相等，并且要求子树所有边的权重之和最小，求出最小值并输出子树的边号。
修改版dij。在最短路的时候，每个点存它被松弛的那条边，这条边尽量在保证最短路的情况下最小。因为这样就能使边能够更加合理利用，贪心思想。
Codeforces 711D
题意：给一个图，$n$个点$n$条边，可以让任意几条边方向取反，问有多少种方案使得图中没有环。
对于一个环，要使得它环被破坏，那么必须取反环上的一些边，不能不反或者全反，否则新的环将出现。因为图中给出$i->a_i$边的图每个点出度至多为1，所以没有大环包含小环的情况，也没有取反一条边后形成新环的可能，因为路径$u->v$如果取反一条边后形成新环，则$u->v$一定存在，与出度至多为1矛盾。所以每个环对答案的贡献为$2^{k_i}-2$, $k_i$为环$i$的大小。不在任何环上的点指出的边可以任意取反或不取反，对环的构成无影响。根据乘法原理，得到最终答案为$2^{n-\sum_{i=1}^{siz}k_i}\prod_{i=1}^{siz}(2^{k_i}-2)$，$siz$为环的总个数
知识点：1、DFS 开一个 cnt 数组辅助求解有向环
2、图中给出$i->a_i$边的图每个点出度至多为1，所以没有大环包含小环的情况。
Codeforces 740D
题意：给出一棵有根树，树上每个点、每条边都有一个权值。现在给出“控制”的定义：对一个点$u$，设点$v$在其子树上，则称$u$控制$v$。要求求出每个点控制了多少个点
我们从根向下 DFS。对于一个点，他上面距离他点权长的点都是控制这个点的。只要找到这个临界点即可。由于树边权为正，所以边权前缀和为单调序列，用二分找。用倍增也行。然后这一段就+1，树上差分即可。
知识点：
1、一定要在纸上写思路！不管多简单的题目，只要是这种 50 行以上的
2、不要看错题目！仔细看，有必要将简要题意写下来！
3、正数前缀和-单调性-二分
Codeforces 918D
题意：一个 DAG 图，边权是小写字母，两人玩游戏，他们起点分别是$i$和$j$节点，每次可以沿出边方向移动一格，前提是该边的字母大于等于上一轮移动经过的边的字母，不能移动的就输，问所有$i$和$j$为起点结果谁能赢。
设$dp(t,i,j)$为当前限制字母$t$下，先手在$i$, 后手在$j$时先手是否获胜。
那么直接记忆化搜索转移即可，注意交替先后手，如果当前后手无法移动则当前先手获胜。
知识点：博弈 DP 核心为先手后手状态 + 交替先手后手求解。
Codeforces 954D
题意：$n$个顶点$m$条边的无向图，现要求添加一条边并且不改变$st$的最短路，问有多少种可行的情况
对于两个点之间加一条边，$dis(s,i)+1+dis(j,t)$和$dis(t,i)+1+dis(j,s)$都不能比最短路短，否则这条路径就成为了最短路。所以预处理$s,t$到每个点的最短路，然后$O(n^2)$枚举$dis(s,i)+1+dis(j,t)$和$dis(t,i)+1+dis(j,s)$都大于等于最短路的边(点对)。
知识点：本题运用了最短路更新的三角不等式的性质，本题加边不能破坏原有的三角不等式性质，否则这条路径就是最短路了，充分运用了最短路的性质，与树的直径证明很像。
Codeforces 920E
题意：给你一个无向图，求它补图的连通分量个数以及所有连通分量的大小，升序输出。
这题也就只能 BFS 暴力了，最开始将所有点放进一个数组，然后每次从里面拿一个出来 BFS 扩展，然后每一层扩展到的点实际上是不可达的，要把没有扩展到的点加进队列，并且在数组中删除。这样找出来就是一个联通分量了。但是数组要支持删除很慢，我们就用链表来做。
知识点：链表让数组支持$O(1)$删除，BFS取没有扩展的点加入队列的思想很好。
Codeforces 999E
题意：给你$n$个点，$m$条边，以及一个初始点$s$，问你至少还需要增加多少条边，使得初始点$s$与剩下其他的所有点都连通。
由于图中可能有环，并且一个环其中一点能到达首都则其他点都可以到达。所以用 Tarjan 对原图缩点然后变成一个 DAG 图。之后统计入度为 0 的点即可，但是要小心从首都出发的链，将这些链先标记，然后每次查找到入度为 0 的点 DFS 看这个点所在链是否全部标记，没有全部标记就可以连一条边到首都。DFS 必要的标记还是要打上qwq，不然 TLE 到死啊
知识点：1 Tarjan小心新图原图区别 2 DFS 必要的标记还是要打上qwq