n遍Floyd
普通的Floyd的枚举顺序：
for (k) for (i) for (j)
dis[i][j] = min(dis[i][k] + dis[k][j])
这样的Floyd求出的最短路是不限边数的。
而如果写成这样：
for (i) for (j) for (k)
diss[i][j] = min(dis[i][k] + a[k][j])
（其中 (diss) 为初始化全为inf的矩阵，(dis,a) 初始为邻接矩阵，无边则为inf）并且最短路就为借助一个点的最短路。
如果做 (n) 遍 Floyd（Floyd后注意更新dis矩阵，这时(dis) 矩阵表示借助 (n-1) 个点的最短路），则为恰好借助 (n) 个点的最短路（经过 (n+1) 条边）。
遍数可以用矩阵加速（矩阵乘法的res[i][j] += a[i][k] * b[k][j]改成res[i][j] = min(res[i][j], a[i][k] + b[k][j])即可。
当然，如果真的完全按照矩阵乘法的规则进行计算的话，矩阵的 (k) 次方的第 (u) 行第 (v) 列就是从 (u) 到 (v) 经过恰好 (k) 条边的方案数。例题：CF402E Strictly Positive Matrix
树的直径
性质：
-
树中最长路径。
-
不一定唯一。
-
树中距离任意点 (u) 的最远点 (v) 一定是直径的端点之一。
求法：
先随意指定一个点，BFS找出树上距离该点最远点 (u)；再从 (u) 开始，BFS找出树上距离 (u) 的最远点 (v)。 (u -> v) 即为树点直径之一。
树的重心
性质：
-
树的重心是树中以某点为根，最大子树最小的那个节点。
-
树的重心是树中所有点到某点的距离之和最小的那个节点。
-
树的重心的所有子树的大小不超过整棵树大小的一半。其逆命题成立。
-
树的重心一定不超过两个。如果树的节点数为奇数，那么重心只有一个；否则可能有两个。
-
添加一个节点，树的重心最多只会移动一个位置。
-
将两棵树连接，新树的重心一定在两棵树的原重心的连线上。
-
以 (rt) 为根的树的重心一定是 (rt) 或 (rt) 的重儿子 或 (rt) 的重儿子的重儿子...
求法：
树形dp，维护最大子树的大小。选取最大子树最小的那个点作为根。
详见点分治
重心的动态维护1
支持加边，查重心。
详见：P4299 首都
LCT 动态加边；并查集维护森林；
运用后两条性质，加边后提取出两个重心的链来，在链的Splay上做树上二分即可。
重心的快速维护2
求以 (rt) 为根的所有子树的重心((n <= 2e5))
方法一：将两棵树连接，新树的重心一定在两棵树的原重心的连线上。
我们自然可以沿用“重心的动态维护1”的方法，(DFS) 动态加边；但是更暴力的是，我们可以直接跳链查询。可以感性地知道这样做的复杂度不会很高。（因为重心的优美性质）（不到 (O(n ^2)))。上 LCT 能到 (O(nlogn))
方法二：以 (rt) 为根的树的重心一定是 (rt) 或 (rt) 的重儿子 或 (rt) 的重儿子的重儿子...
我们可以利用 以 (rt) 为根的树的重心一定是 (rt) 或 (rt) 的重儿子 或 (rt) 的重儿子的重儿子... 的性质，这样我们就知道了重心的位置在一条链上。并且，我们发现，重心的 (n - siz <= n / 2)（显然），并且链上这个条件是单调的。最深的符合该条件的点一定是重心（可以贪心证明），其父亲可能是重心。因此倍增查找具体位置即可。
复杂度： (O(nlogn))
重心的快速维护3（2的加强版）
查询：删每一条边后分成的两棵树的重心。
详见：P5666 树的重心
实际上这道题放在 (D2T2) 或 (D1T3) 或许会有更多人写出来。
由于操作与操作之间不相关，因此我们需要动态加边，删边，查重心，这就不能用上面的 (LCT) 算法了（况且我当时连 (Splay) 都不会）
部分分55pts很好拿，考虑怎样拿到剩下的45pts.（(n<=3e5)) 由于需要维护所有边删掉后的信息，整个数据只有一棵树，我们应该能想到换根DP。（然而当时我并不会换根DP）
如果只删一次边，那么我们 (O(n)) 怎么搞都行，但是如果删很多次边，由于传统的算法里面涉及到的 (Siz) 和 (siz) 会变，我们不能够利用传统算法里面的 (f[]) 之类的数组。那还有什么东西可用呢？
很显然的一条性质："以 (rt) 为根的树的重心一定是 (rt) 或 (rt) 的重儿子 或 (rt) 的重儿子的重儿子..." 根据这一条性质我们能够 (O(nlogn)) 地维护以 (1) 为根的所有子树的重心。（见“重心的快速维护2”）
我们可以把问题拆成两部分:“分离”出的子树重心，和整个树的残缺部分的重心。前者可以用前面的方法快速地求出；这里只讨论后者。
如果我们考虑随意删一条边的话， (son) 的变化比较大，不太好维护。根据换根DP的思想，我们只考虑删掉与根节点相连的一条边。这样的话， (son) 最多只改变一个，维护一个 (sson)（次重儿子）即可。
这样，我们就用 (O(nlogn)) 的方法解决掉了 (CSP ~ 2019 ~ D2T3) 了。
需要卡常。
重心的动态维护4
给一棵无根树，度数均不超过60，支持修改点权，以及查询：
题解：
根据重心的性质：
树的重心是树中所有点到某点的距离之和最小的那个节点。
我们知道那个和式取最小值当且仅当 (p) 为树的重心。加权了也没关系，看作一条内部边权均为0的链即可。
那么我们需要快速地维护树的重心。设 (F(x) = sum_{u}val[u] * dis(u,x))，上面 CSP2019D2T3 告诉我们可以用倍增预处理“重儿子链”的方式来快速求重心，并且我们可以换根 DP (O(n)) 求所有的 (F(x))，但是如果要支持修改点权的话，轻重边可能会改变，暴力修改“重儿子链”并修改倍增数组很可能会被卡成 (O(qnlogn))，且所有的 (F(x)) 都会改变，这个方法将沦为比暴力还暴力的暴力。我们还要想其它的法子。
不过，幸运的是，“根据重儿子判断重心的大致位置”的思想在这道题里面仍然适用。我们想，如果我们瞎选一个点，并且知道它的重儿子是谁，就可以去重儿子的子树里面寻找答案。这看起来很像是一个子问题。如果我们能够保证“去子树”的次数不是很多，就能解决这个问题了。因此我们使用点分治来维护重心。
现在还有两个问题：如何快速求 (F(x))，以及如何快速找重儿子。
感性地理解一下（其实理性证明也不难），(F(heavy~son) <= F(cur))，又因为度数 <= 60，所以两个问题转化为一个问题。这个问题交给点分治解决好了
根据套路，维护一个 (g(x))，表示 (x) 管辖区域的点权和。维护一个 (f1(x))，表示 (x) 管辖区域内所有“点”（权值为 (v) 的点视为 (v) 个点）到 (x) 的距离之和。维护一个 (f2(x))，表示 (x) 管辖区域内所有“点”到 (fa(x)) 的距离之和。其中 (fa(x)) 表示 (x) 在点分树上的父亲。
然后套用 震波 的方法，一层一层地算贡献。对每一层算一下当前层的贡献，减去多算的上一层的贡献。复杂度：单次 (O(logn))。
这样，我们不直接维护重儿子，修改就没必要 (O(n)) 的改所有点的重儿子了。
总复杂度：(O(nlogn + degree * qlog^2n))由于度数 <= 60，因此可以通过此题。
欧拉序维护LCA
这是一种 (O(nlogn)) 静态维护LCA (O(1)) 查询的方法：
对一棵有根树进行DFS，每次进入或返回到某个点的时候都给那个点一个新编号，并且将这个点放到一个序列（欧拉序）里面。查询的时候就直接查 (u) 和 (v) 的编号之间的最小编号即可。借助ST表，我们可以做到 (O(1)) 查询。
LCA的巧用
三点间路径交叉点
这是一个经典的问题：给三点 (x, y, z)，求路径的交点（即 (x) 到 (y,z) 路径的最近点）。
我们可以找出三个点的两两之间的LCA，记作 (lca1, lca2, lca3)，最终答案为 (lca1 ~ xor ~ lca2 ~ xor ~ lca3)。
这是因为，这仨LCA必定有两个是一样的，并且还是较高的那一个。然后剩下那个较低的LCA即为交点。
两路径求交
其次是一个略复杂的问题：给两条路径 ((u,v)) 和 ((p, q))，询问这两条路径是否相交。
我们可以搞出 (lca(u,p),lca(u,q),lca(v,p),lca(v,q))。其中一定有俩是 (lca(u,v,p,q))。如果两路径相交，那么剩下俩之间的路径就是交的那一部分路径；否则，剩下俩一定相等，并且位于两路径中LCA较高的那一条，而不位于LCA较低的那一条。由此我们可以判断是否相交以及找出相交部分的路径。
一个比较简单的结论:两条路径有交当且仅当一条路径的 LCA 被另一条路径经过
一些情况：
DFS 树
DFS 树是 tarjan 算法中的强有力工具，也是解决某些(CF)图论题目的好方法。
无向图 DFS 树
定义 无向图的 DFS 树上的边 为树边，那么无向图的边只有树边和祖先-子孙边，不会出现横叉边（显然)
应用：tarjan
有向图 DFS 树
定义 有向图的 DFS 树上的边 为树边，那么有向图的边只有树边和祖先->子孙边，子孙->祖先边，横叉边（后遍历的点 -> 先遍历的点）
应用：tarjan