算法详解：树形DP中的树的重心求解

算法详解：树形DP中的树的重心求解

引用

CSDN

1.

https://blog.csdn.net/weixin_74850661/article/details/146164196

在树的算法中，求解树的中心和重心是一类十分重要的算法。本文将详细介绍树的重心的概念、求解方法，并通过一个实践题目加深理解。

树的重心概念

树的重心的定义：重心是树中的一个节点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点称为树的重心。

求解树的重心

求解重心需要记录的值：

• 由于重心关注的是删除一个节点之后，剩余的连通分支中点的最大值，然后这个值要求是最小的，然后需要返回这个最小化的最大值。

删除一个节点之后，会分为几个部分：

• 节点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

重心实践题目：小红的陡峭值

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

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)