2020-2021:teams:hotpot:diameterandweight
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:hotpot:diameterandweight [2020/06/11 12:26] misakatao 更新 |
2020-2021:teams:hotpot:diameterandweight [2020/06/11 12:35] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 23: | 行 23: | ||
| ======树的直径求解====== | ======树的直径求解====== | ||
| - | 第一种方法是利用性质2，首先从任意一个点开始bfs，找到一个离这个点最远的点，这样就找到了直径的一端，然后我们从这个点再开始bfs就可以同时找出直径的长度和直径的两端。但这种方法的缺点是不能处理有负权的情况。代码实现十分简单，这里就不给出了。 | + | 第一种方法是利用性质2，首先从任意一个点开始bfs，找到一个离这个点最远的点，这样就找到了直径的一端，然后我们从这个点再开始bfs就可以同时找出直径的长度和直径的两端。但这种方法的缺点是不能处理有负权的情况。代码实现十分简单，这里就不给出了。时间复杂度$O(n)$。 |
| 第二种方法是树形DP，令$f_1[i]$表示节点$i$到它叶子节点路径长度的最大值，$f_2[i]$表示节点$i$到它叶子节点路径长度的次大值，我们只需要按照正常记录最大值和次大值的方法更新，最后的答案即为$max\{ f_1[i] + f_2[i] \}$，这一方法可以处理负权，但是很难确定直径的两端是哪两个节点。代码实现可以看[[https://blog.csdn.net/forever_dreams/article/details/81051578|这篇博客]] | 第二种方法是树形DP，令$f_1[i]$表示节点$i$到它叶子节点路径长度的最大值，$f_2[i]$表示节点$i$到它叶子节点路径长度的次大值，我们只需要按照正常记录最大值和次大值的方法更新，最后的答案即为$max\{ f_1[i] + f_2[i] \}$，这一方法可以处理负权，但是很难确定直径的两端是哪两个节点。代码实现可以看[[https://blog.csdn.net/forever_dreams/article/details/81051578|这篇博客]] | ||
| 行 140: | 行 140: | ||
| printf("%d\n",ans); | printf("%d\n",ans); | ||
| return 0; | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | |||
| + | ======树的重心及其性质====== | ||
| + | |||
| + | 树的重心的定义为，树的所有点中，以某一个点为根，最大的子树大小最小的点。 | ||
| + | |||
| + | 树的重心有这些性质： | ||
| + | |||
| + | 1.树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个距离和，他们的距离和一样。 | ||
| + | |||
| + | 2.把两棵树通过一条边相连，新的树的重心在原来两棵树重心的连线上。 | ||
| + | |||
| + | 3.一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置。 | ||
| + | |||
| + | 4.一棵树最多有两个重心，且相邻。 | ||
| + | |||
| + | 树的重心一般在点分治等算法中应用。 | ||
| + | |||
| + | ======树的重心的求解====== | ||
| + | |||
| + | 树的重心可以用树形DP的方式求解，以任意一个点为根，每到一个点记录这个点的每颗子树的大小，并把除了以这个点为根的子树意外的部分也当作一个子树，找到其中大小最大的并记录，整体找到记录值最小的点就是重心，时间复杂度为$O(n)$。递归部分代码如下 | ||
| + | |||
| + | <code cpp> | ||
| + | inline void find(int x, int fa, int siz) | ||
| + | { | ||
| + | size[x] = 1; | ||
| + | int sons = 0; | ||
| + | for(int i = F[x];i != -1;i = nex[i]) | ||
| + | { | ||
| + | int t = v[i]; | ||
| + | if(t == fa) | ||
| + | continue; | ||
| + | find(t, x, siz); | ||
| + | if(size[t] > sons) | ||
| + | sons = size[t]; | ||
| + | size[x] += size[t]; | ||
| + | } | ||
| + | if(siz - size[x] > sons) | ||
| + | sons = siz - size[x]; | ||
| + | if(num > sons) | ||
| + | num = sons, g = x; | ||
| } | } | ||
| </code> | </code> | ||
2020-2021/teams/hotpot/diameterandweight.1591849567.txt.gz · 最后更改: 2020/06/11 12:26 由 misakatao
