AcWing 846. 树的重心
原题链接
简单
作者:
Zhebao
,
2024-04-06 14:40:22
,
所有人可见
,
阅读 1
#构建邻接表
n = int(input())
tree = [[] for i in range(n + 1)]
for _ in range(n - 1):
a,b = map(int,input().split())
tree[a].append(b)
tree[b].append(a)
total = n #总节点数
min_nodes = n #最小的最大连通块的节点数
cent = 1 # 重心
def dfs(u,parent):
global total,min_nodes,cent
size = 1 # 当前点的子树大小
max_part = 0 # 删除当前节点后最大部分节点数
for v in tree[u]:
if v == parent: #避免循环,相当于visited数组
continue
subtree_size = dfs(v,u) #递归计算子树的大小
size += subtree_size
max_part = max(max_part,subtree_size)
max_part = max(max_part,total - size)
if max_part < min_nodes:
min_nodes = max_part
centroid = u
return size
dfs(1,-1)
print(min_nodes)