题目描述

给定一颗树，树中包含n个结点（编号1~n）和n-1条无向边。

请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

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

思路：

1.除去重心后的连通块包括两类，一类为重心节点子树若干连通块，一类是除去重心节点及其子树的连通块
2.第一类的求法：通过DFS计算每个节点子树连通块的最大值
2.第二类的求法：通过树节点总数n 减去 重心节点所有子树和 即 n - size4

关键变量：
ans  各个节点连通块的最大值的最小值
st 标记数组
sum 当前节点及子树的点数量
res 记录除去当前节点的连通块最大值
s 当前节点的子树节点数量

核心代码：
def dfs(u):
    global ans # 最大连通块的最小值
    st[u] = True
    
    sum = 1 # 当前节点数为1
    res = 0 # 子树连通块数量
    
    i = h[u]
    while i != -1:
        j = e[i]
        if !st[j]:
            s = dfs(j)
            res = max(res,s)
            sum += s
        i = nxt[i]
    res = max(res,n-sum)
    ans = min(ans,res)
    return sum
完整代码： 
import numpy as np
def main():
    global e,nxt,h,idx,st,n
    global ans
    ans = 100010

    idx = 0
    n = int(input("请输入整数n:"))
    e = np.full((n,),-1,dtype=int)
    nxt = np.full((n,),-1,dtype=int)
    h = np.full((100,),-1,dtype=int)
    st = np.full((100,),False,dtype=bool) #标记数组
    m = n-1
    while m:
        a = int(input("请输入a:"))
        b = int(input("请输入b:"))
        add(a,b)
        m -= 1
    dfs(1)
    print(ans)

# 头插法建立链表
def add(a,b):
    global idx
    e[idx] = b
    nxt[idx] = h[a]
    h[a] = idx
    idx += 1

# 求 u节点的子树个数
def dfs(u):
    global ans
    st[u] = True

    sum = 1 # 当前子树中点的数量
    res = 0 # 连通块最大值

    i = h[u]
    while i!=-1:
        j = e[i]
        if st[j] == False:
            s = dfs(j) # 当前子树大小,dfs返回j的子数大小
            res = max(res,s)
            sum += s
        i = nxt[i]

    res = max(res,n-sum) # n-sum 是指除去u节点子树外，连通块大小
    ans = min(ans,res)

    return sum


if __name__ == '__main__':
    main()