算法-之-树形dp-树的中心重心
目录
算法 之 树形dp 树的中心、重心
- 在树的算法中，求解树的中心和重心是一类十分重要的算法
求解树的重心
- 树的重心的定义：重心是树中的一个节点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点称为树的重心
- 求解重心需要记录的值：由于重心关注的是删除一个节点之后，剩余的连通分支中点的最大值，然后这个值要求是最小的，然后需要返回这个最小化的最大值。
删除一个节点之后，会分为几个部分，节点u的所有子树所独立出来的子树，以及原本的树删除以u为根节点的树- 所以要记录，
u的所有子树当中，size子树的最多节点数，sumnunm以u为根节点的节点数(用于dfs的返回值)，n-sumnum除去以u为根节点的剩余部分的节点数 - 值得注意的是，遍历的之后是从根节点到叶子节点，但是我们是在
归(叶子节点到根节点)中的过程中，更新答案的 - 由于是 无向图，所以要么
设置vis[i]标记节点是否访问过,要么设置dfs(u,fa)其中fa是u的父亲节点
c代码
int dfs(int u)
{
vis[u] = true; //为了不重复搜索，所以得标记
int size = 0; // 记录u的子树中的最大节点数
int sum = 1; // 记录以u为根节点的子树的节点总数
for(int i = h[u];i!=-1;i=ne[i])
{
int j = e[i];
if (vis[j]) continue;
int s = dfs(j);
size = max(size,s);
sum += s;
}
ans = min(ans,max(size,n-sum));
return sum;
}python代码
# 使用邻接表来存储点之间的边关系
g = [[]*n ]
vis = [False]*n
ans = n
def dfs(u):
global ans
vis[u] = True
sumnum = 1 # 记录以u为根节点的子树的总节点数
size = 0 # 记录 u的子树当中最大的节点数
for v in g[u]:
if vis[v]: continue # 如果访问过就跳过
s = dfs(v) # 求解出以v为根节点的子树的节点数
size = max(size,s) # 更新答案
sumnum += s
# 更新这个ans
ans = min(ans,max(size,n-sumnum))
return sum
重心实践题目
小红的陡峭值
- 这题与求解重心的思路十分相似：都是删除一部分，关注剩余的部分的情况
- 不一样的是，由于删除的是
边，所以只会将原本的树分为两个部分，但是还是存在一个对应的关系
| 求解重心 | 求解陡峭值 | |
|---|---|---|
| 总的值 | 定点数n | 全部边的陡峭值esum |
| 删除的部分 | 顶点 | 边 |
| dfs返回的值 | 以u为顶点的子树的总顶点数 | 以u为顶点的子树的陡峭值 |
| 关注的部分 | 以u为顶点的子树当中，顶点的最大数，这个数目会被拿去更新ans | 并不关心以u为顶点的子树的陡峭值的最值，而是对于每一个子树的情况都会拿去更新ans |
import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
g = [[] for _ in range(n+1)]
# 类似于求解这个 重心的问题，问题的关键在于从根到叶子，同时在叶子返回这个根的时候动态更新答案
esum = 0
for i in range(n-1):
u,v = map(int,input().split())
g[u].append(v)
g[v].append(u)
esum += abs(u-v)
ans = float("inf")
vis = [False]*(n+1)
def dfs(u):
global ans
vis[u] = True
# 需要记录以u为根的陡峭值，以及子树的陡峭值
sumnum = 0
for v in g[u]:
if vis[v]:
continue
s = dfs(v)
sumnum += abs(u-v) + s
# 更新答案
ans = min(abs(esum-abs(u-v)-s-s),ans)
return sumnum
dfs(1)
print(ans)