图论
最短路
迪迦哥斯拉
某死了算法
Floyd 传递闭包
矩阵优化
定长最短路
同余最短路
最小生成树
Prim
Kruskal
次小生成树
Kruskal 重构树
最大化最小边权
处理某些删边后询问连通块信息的问题
二分图
判断方法
黑白染色
并查集
最大匹配
匈牙利算法
最大权完美匹配
KM 算法 <---------------
性质
最小点覆盖 = 最大匹配 <---------------
最大独立集 = n - 最大匹配 <---------------
DAG 路径覆盖 <---------------
可以相交
把 (u, v) 扩展到 (u, n + v)，答案为 n - 最大匹配
不能相交
先 Floyd 把可达性传递闭包，转化为上一种情况
图的连通性
无向图
点双
注意点
一个割点可以存在至少两个分量中
判断是否处在同一个点双连通分量
记录弹栈的点，bl[u]==bl[v] || pts[bl[u]]==v || pts[bl[v]]==u
维护方法
圆方树
边双
求解细节
在 tarjan 最后弹出当前点所在分量，而非割边相同位置
性质
缩点后是一棵树
有向图
关键
instack
性质
缩点后是 DAG
树
性质
点减边容斥：连通块个数 = 点数 - 边数
只有加边的问题：考虑先把最终树的形态确定下来，就能适用我们熟悉的算法
直径
性质
唯一中点
中点到别的点的最大值最小
求法
两边 dfs（边权非负）
dp
线段树维护
处理方法
把直径拉下来
以直径一端为根
性质
拼接后的直径端点在原先四个中选两个
最小拼接是连接两个直径中点
重心
性质
重心只能有一个或两个
若两个，则相邻，断开这条相邻边后，两个子树大小相同
以重心为根，所有子树大小不超过整棵树大小一半
连接两棵树，新的重心在原先两个重心的路径上
到所有点的距离之和最小
动态维护方法
均摊分析，每次跳一步
计数、统计类问题
在 lca 处考虑合并
树上差分
点权
++p[u], ++p[v], --p[lca], --p[fa[lca]]
边权
边权下放到点权
++p[u], ++p[v], p[lca]-=2
LCA
求法
倍增法
欧拉序（死了）
DFS 序
tarjan（半死不活，一次没用过）
倍增
小 trick
对于 u 跳到祖先 v，但是要扣掉 u 的子树
维护第一步跳的时候处理，这样还是不重不漏的
树剖
重链剖分
性质
一个点往上跳不超过 log 条重链
能够求解
子树加、链加、LCA
解法
两遍 DFS，第二次搞 DFS 序，先遍历重儿子
同一条重链上 DFS 序连续，可以使用数据结构维护
长链剖分
性质
一个点往上跳不超过 sqrt 条重链
解决问题
光速求 kth-fa
继承重儿子信息，优化 DP
倍增和重链剖分异同点
相同点
可以 O(log n) 往上跳，维护信息
不同点
树剖支持修改，适用范围更广
对于动态加叶子的问题，倍增能更好处理，但是离线预处理建树后树剖也能
DFS 栈
使用栈实时维护根到当前点的信息
DFS 差分
记录进入子树的信息，递归完子树后再查看，两者作差就得到了子树内的信息
树上启发式合并
特点
问题可以离线，和子树统计有关
问题一般可以用上很吊的数据结构解决
时间复杂度：线性对数
解决办法
先 redfs 轻儿子，然后删除，redfs 重儿子，加入轻儿子，加入自己，得到自己的答案
虚树
题目特点
m 次询问某些结点，结点数量之和有限制（不然怎么读入啊）
通常可以根号分治
建树方法
单调栈法
二次排序法
点分治
基础点分治
解决问题
树上路径问题
所有路径统计问题
关键函数
getroot
getsiz
solve
点分树
问题特点
有修改
解决方法
把分治中心向上一层连边，形成一棵树
修改、询问跳树的 FA，然后统计答案
注意点
会破坏原树的结构
trick
dfs 序扣除当前分治中心所在连通块，需要扣除 key 的子树
特殊的树
基环树
解题方法
分类讨论，做树上 DP，再做环上 DP
断开环上的一条边，分类讨论，跑 O(1) 次树形 DP
缩点（？）
最短路径树
性质
祖先到后代的距离是最短路
根节点到其他所有点的距离之和最短
警告
没有祖先关系的点对不满足这个性质
分层图
问题形式
分层图最短路
跑 DAG 上 DP
trick
超级源点
差分约束
最短路求最大解，最长路求最小解
DAG 拓扑排序
注意 du 的预处理，可以先跑一遍拓扑排序预处理出 du
2-SAT
特点
每个点只有两种选择
trick
有些题目需要先枚举一些东西，然后剩下的跑 2-SAT
前后缀优化建图
max-2-SAT
NP-hard，想到这应该是建模错了
解法
跑 tarjan 缩点
逆拓扑序，sccno[u] < sccno[u + n] 则选择 u
暴搜
求字典序最小解
拓展
k-SAT
建立虚点 u_j 表示 val[u]>=j
并强制 u_0=true, u_m+1=false
优化建图
线段树优化建图
区间向区间连边问题
欧拉