算法 之 树形dp 树的中央、重心

• 在树的算法中，求解树的中央和重心是一类十分重要的算法
  

求解树的重心

• 树的重心的定义：重心是树中的一个节点，假如将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点称为树的重心
  
• 求解重心需要记录的值：由于重心关注的是删除一个节点之后，剩余的连通分支中点的最大值，然后这个值要求是最小的，然后需要返回这个最小化的最大值。
  
• 删除一个节点之后，会分为几个部分，节点u的所有子树所独立出来的子树，以及原本的树删除以u为根节点的树
  
• 所以要记录，u的所有子树当中，size子树的最多节点数，sumnunm以u为根节点的节点数(用于dfs的返回值)，n-sumnum除去以u为根节点的剩余部分的节点数
  
• 值得注意的是，遍历的之后是从根节点到叶子节点，但是我们是在归(叶子节点到根节点)中的过程中，更新答案的
  
• 由于是 无向图，所以要么设置vis标记节点是否访问过,要么设置dfs(u,fa)此中fa是u的父亲节点
  

• c代码
  
  
  
  

1. int dfs(int u)
2. {
3.         vis[u] = true; //为了不重复搜索，所以得标记
4.         int size = 0; // 记录u的子树中的最大节点数
5.         int sum = 1; // 记录以u为根节点的子树的节点总数
6.         for(int i = h[u];i!=-1;i=ne[i])
7.         {
8.                 int j = e[i];
9.                 if (vis[j]) continue;
10.                 int s = dfs(j);
11.                 size = max(size,s);
12.                 sum += s;
13.         }
14.         ans = min(ans,max(size,n-sum));
15.         return sum;
16. }

复制代码

• python 代码
  

1. # 使用邻接表来存储点之间的边关系
2. g = [[]*n ]
3. vis = [False]*n
4. ans = n
5. def dfs(u):
6.         global ans
7.         vis[u] = True
8.         sumnum = 1 # 记录以u为根节点的子树的总节点数
9.         size = 0 # 记录 u的子树当中最大的节点数
10.         for v in g[u]:
11.                 if vis[v]: continue # 如果访问过就跳过
12.                 s = dfs(v) # 求解出以v为根节点的子树的节点数
13.                 size = max(size,s) # 更新答案
14.                 sumnum += s
15.         # 更新这个ans
16.         ans = min(ans,max(size,n-sumnum))  
17.         return sum
18.          

复制代码

重心实践标题

小红的陡峭值

小红的陡峭值

• 这题与求解重心的思路十分相似：都是删除一部分，关注剩余的部分的情况
  
• 不一样的是，由于删除的是边，所以只会将原本的树分为两个部分，但是照旧存在一个对应的关系
  

求解重心求解陡峭值总的值定点数n全部边的陡峭值esum删除的部分顶点边dfs返回的值以u为顶点的子树的总顶点数以u为顶点的子树的陡峭值关注的部分以u为顶点的子树当中，顶点的最大数，这个数目会被拿去更新ans并不关心以u为顶点的子树的陡峭值的最值，而是对于每一个子树的情况都会拿去更新ans

1. import sys
2. sys.setrecursionlimit(10 ** 6)
3. n = int(input())
4. g = [[] for _ in range(n+1)]
6. # 类似于求解这个 重心的问题，问题的关键在于从根到叶子，同时在叶子返回这个根的时候动态更新答案
7. esum = 0
8. for i in range(n-1):
9.     u,v = map(int,input().split())
10.     g[u].append(v)
11.     g[v].append(u)
12.     esum += abs(u-v)
14. ans = float("inf")
15. vis = [False]*(n+1)
17. def dfs(u):
18.     global ans
19.     vis[u] = True
20.     # 需要记录以u为根的陡峭值，以及子树的陡峭值
21.     sumnum = 0
22.     for v in g[u]:
23.         if vis[v]:
24.             continue
25.         s = dfs(v)
26.         sumnum += abs(u-v) + s
27.         # 更新答案
28.         ans = min(abs(esum-abs(u-v)-s-s),ans)
29.     return sumnum
30. dfs(1)
31. print(ans)

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。