你好，我是 zbl2012 👋

树的直径就是树上两点的最远距离。 如果暴力 dfs 会发现，最后情况下每一次都把树跑满，时间复杂度 On^2，显然是不可以通过 10^5 的数据的。 考虑优化成 On。 假设有一点 x，通过一次 On 的 dfs 找到了自己的最远的是 y，此时发现，如果再跑一次以 y 为起点的 dfs，这个 dfs 中的跑的距离就是答案了。 注意点 1.实现时 dfs 中的边界。 cod...

树的重心就是在一个树里，删去一个节点，使剩下的最大联通快最小。 我们要在 On 的时间内，求出这个重心。 如果每一个节点当根，每一个都跑一遍 dfs 的话，时间复杂度是 On^2，显然不可以通过。 所以就要用到一个技巧：换根。 首先，我们要用 dfs 求出以 1 为根的每个节点的子树大小和父节点。然后就是换根环节了，随便观察一个树以 1 为根时的每个节点的子树大小，会发现：当换成 ...

Kruskal Kruskal 求最小生成树是一种以边贪心的最小生成树算法。 设一张图的点数为 n，边数为 m。 观察一个图和它的最小生成树，发现在构造最小生成树的过程中，每一次是选择一条较小的边去连通，所以考虑贪心。 首先肯定是按边权从小到大排序，然后跑每一条边。如果这个边得起点和重点没有放进最小生成树的集中，就把他们放进集合，并将答案加入边权，总边数 +1。如果在跑的过程中，总边...

学了AC自动机的拓扑排序优化，故来补一下。 拓扑排序是一种在DAG有向无环图上求解关于先后顺序的算法。其中它排序出来的结果叫做拓扑序。 拓扑排序其实可以抽象化成家谱：给定每个人的子辈，求所有人的辈分排序。 拓扑排序本质上就是一个 bfs。 首先遍历所有点，把入度为 0 的点找出来，不难证明，这些点就是最高辈分的那些点，因为他们都没有父节点。把这些点入队，然后跑 bfs，将队头的...