P1670 [USACO04DEC] Tree Cutting S - 洛谷 树的重心模版，题面意思即是定义二。
P1395 会议 - 洛谷 树的重心模版。
P2986 [USACO10MAR] Great Cow Gathering G - 洛谷 树的带权重心。
树的重心有如下三种定义，求出来的点是一样的
- 以某个节点为根时，最大子树的节点数最少，那么这个节点是重心
- 以某个节点为根时，每颗子树的节点数不超过总节点数的一半，那么这个节点是重心
- 以某个节点为根时，所有节点都走向该节点的总边数最少，那么这个节点是重心
补充性质：
- 一棵树最多有两个重心，如果有两个重心，那么两个重心一定相邻
- 如果树上增加或者删除一个叶节点，转移后的重心最多移动一条边
- 如果把两棵树连起来，那么新树的重心一定在原来两棵树重心的路径上
- 树上的边权如果都为正数，不管边权怎么分布，所有节点都走向重心的总距离和最小
最常用的求重心的方法为第一个和第二个。
定义一具体代码为
sz = [0] * (n + 1)
core = [] # 树的重心数组
MX = infdef dfs(u, fa=-1):nonlocal core, MXsz[u] = 1mx = 0for v in g[u]:if v != fa:dfs(v, u)sz[u] += sz[v]mx = Max(mx, sz[v])mx = Max(mx, n - sz[u])if mx < MX: # 定义一MX = mxcore = [u] # 不断更新最大子树的最小节点数elif mx == MX:core.append(u)
dfs(1)
定义二具体代码为
sz = [0] * (n + 1)
ans = []def dfs(u, fa=-1):sz[u] = 1mx = -1for v in g[u]:if v != fa:dfs(v, u)sz[u] += sz[v]mx = Max(mx, sz[v])mx = Max(mx, n - sz[u])if mx <= n // 2: # 定义二ans.append(u)
dfs(1)
在树上，如果存在一点使得 \(\sum(dist(u,v)\times w_v)\) 最小的节点，就是树的带权重心。这是树的重心的一个很重要的性质。
这里使用方法二求解问题二。
sz = [0] * (n + 1)
core = 0def dfs(u, fa=-1):nonlocal coresz[u] = weight[u - 1] # 这里不再是默认的1了，而是有自己的点权mx = 0for v, _ in g[u]: # 忘记节点附带了边权，没有解包if v != fa:dfs(v, u)sz[u] += sz[v]mx = Max(mx, sz[v])mx = Max(mx, s - sz[u])if mx <= s // 2: # 定义二core = udfs(1) # 忘记调用函数了