2025暑期日志

· · 个人记录

Day 1

今天讲的是图论，比较简单的一种，树——
树的直径：在一棵树内，最长的一段边，求解方式，可以用两遍DFS求解，也可以用树上DP求解，转移方程为

\hspace{1cm}$ $f_u = max (f_u,f_v + w) 
$f[i]$代表以$i$为根往下延伸到的最大深度，但显然这不一定是最终的答案，所以我们最终的答案要取最大的值和次大的值之和，即 ——
\hspace{1cm}$ $ans = max (ans,f_u + f_v + w)

这就是树的直径。例题

树的重心 ：
定义

如果在树中选择某个节点并删除，这棵树将分为若干棵子树，统计子树节点数并记录最大值。取遍树上所有节点，使此最大值取到最小的节点被称为整个树的重心。

（这里以及下文中的「子树」若无特殊说明都是指无根树的子树，即包括「向上」的那棵子树，并且不包括整棵树自身。）

性质

1.树的重心如果不唯一，则至多有两个，且这两个重心相邻。

2.以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。

3.树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。

4.把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。

5.在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

求法

直接dfs一遍，把不符合条件的都筛去，剩下的点就是重心了

树上差分：
就是在树上求两个点之间的距离，用这两个点距离根节点的距离之和再减去两倍最近公共祖先的距离就是两点之间的距离了。

dfn序：
就是他现在经过的第几个节点，给定了一个新的排序。

树链剖分：
就是把一棵树的重儿子单独拿出来，就是一条链，树链剖分的思想及能解决的问题 树链剖分用于将树分割成若干条链的形式，以维护树上路径的信息。

具体来说，将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息。

树链剖分（树剖/链剖）有多种形式，如 重链剖分，长链剖分 和用于 Link/cut Tree 的剖分（有时被称作「实链剖分」），大多数情况下（没有特别说明时），「树链剖分」都指「重链剖分」。

重链剖分可以将树上的任意一条路径划分成不超过

重链剖分还能保证划分出的每条链上的节点 DFS 序连续，因此可以方便地用一些维护序列的数据结构（如线段树）来维护树上路径的信息。 如： 修改 树上两点之间的路径上 所有点的值。 查询 树上两点之间的路径上 节点权值的 和/极值/其它（在序列上可以用数据结构维护，便于合并的信息）。 除了配合数据结构来维护树上路径信息，树剖还可以用来 $O(\log n)$（且常数较小）地求 LCA。在某些题目中，还可以利用其性质来灵活地运用树剖。 --- # Day 2 图论（2） ： 最短路 ： 1.$dijistra$ 用于正边权，无环，时间复杂度$O(n log n)

2.spfa可以处理负边权和找负环问题，时间复杂度为O(nm)
3.Floyd可以处理找环和最短路，时间复杂度为O(n ^ 3)

判负环：
用spfa直接判就行。

强联通分量：

强连通的定义是：有向图 G 强连通是指， G 中任意两个结点连通。 强连通分量（ SCC ）的定义是：极⼤的强连通⼦图

双联通分量：
在⼀张连通的⽆向图中，对于两个点 u 和 v ，如果⽆论删去哪条边（只能删去⼀条）都 不能使它们不连通，我们就说 u 和 v 边双连通。 在⼀张连通的⽆向图中，对于两个点 u 和 v ，如果⽆论删去哪个点（只能删去⼀个，且 不能删 u 和 v ⾃⼰）都不能使它们不连通，我们就说 u 和 v 点双连通。 对于⼀个⽆向图中的极⼤边双连通的⼦图，我们称这个⼦图为⼀个边双连通分量。 对于⼀个⽆向图中的极⼤点双连通的⼦图，我们称这个⼦图为⼀个点双连通分量。

二分图：

定义：顶点集可以划分为两个互不相交的⼦集，使得图中的每条边都连接这两个集合之 间的⼀对点，⽽不会连接同⼀集合内部的点。 换⼀种定义⽅式：不存在奇环的图。因为我们可以通过⿊⽩染⾊来判断⼀张图是否为⼆ 分图。 具体的实现就是从⼀个点开始⿊⽩染⾊，如果遇到了⼀个染过⾊并且和当前颜⾊相同的 点，就不是⼆分图。