LUOGU_图论
LUOGU_图论
ST表+DFN序LCA
每次在自己的DFN序位置放入自己的父亲
询问的时候l+1
ST表+欧拉序LCA
\(u,v\) 在欧拉序中的第一个位置之间的深度最小位置就是LCA
树的直径
相距最远的两个点
\(\max_{u,v}dis(u,v)=\max_{u,v}(dep_u+dep_v-2dep_{lca(u,v)})\)
边权非负：两次BFS
边权有负：DP
动态维护直径 P6845 Dynamic Diameter：
树的重心
重心最多有两个，无根树计数时如果需要钦定根，可以钦定重心。
最短路
单源最短路
一轮 Bellman-Ford 松弛可以看作一次 \(\{min,+\}\) 矩阵乘法：
\(\textbf{E}^{n-1}\times \vec d\) 则得到最终结果
P6190 魔法：\(\textbf{E}^{n-1}\times (K\times \textbf{E}^{n-1})^k\times\vec d\)
P1266 速度限制：分层图：图论中一个点表示的信息可以是很丰富的，当我们觉得一个点的信息单薄时，可以考虑像 dp 状态加维度一样给点也加一维信息。
P2149 Elaxia的路线：最短路径图，分为同向与异向，处理出同时在最短路上的边，在这上面找最长链即可。
差分约束：\(c_i\le c_j+x\)
P7624 地铁：二分环长上下界，并将环长 $\sum L_i+k\times mid $，将二分的环长与常数分离开，这样可以通过 \(k\) 的正负判断 \(k\) 应该增大还是减小，这样也可以辅助发现合法的答案一定是一个区间。
多源最短路：
全源最短路：
无负环：Dij\(\mathcal O(nm\log m)\)
有负环：Johnson \(\mathcal O(nm\log m)\)
好写+稠密图：Floyed \(\mathcal O(n^3)\)
连通性
P3825 游戏：首先可以枚举 \(x\) 是 \(a,b,c\) 的哪一个 \(\mathcal O(3^d(n+m))\) 跑 2-SAT。但 \(x\) 只需要选择 \(a,b\) 就可以覆盖 \(A,B,C\) 三种情况了，即不论选择 \(A,B,C\) 的哪一个， \(x=a,b\) 中总有一种情况可以统计到。
P5058 嗅探器：DFN序确定相对位置，其实就是求A，B之间的割点，这里以A为根，通过DFN序确定其在树上的相对位置。（告诉我们Tarjan并不只是一个黑盒算法）
弱联通
连通性删边：即删去一些边后连通性不变，在一些有特殊节点的图上，这样往往可以使得最后有用的边所剩无几。
P7737 [NOI2021] 庆典：先缩点，再删边，删成一个叶向树了。
欧拉回路
找欧拉回路通过DFS搜索，并加入当前弧优化。