树的重心
一句话说明
树的重心就是“删掉它以后，剩下的最大连通块最小”的那个点。
Go 代码
func findCentroid(n int, edges [][]int) int {
g := make([][]int, n)
for _, e := range edges {
u, v := e[0], e[1]
g[u] = append(g[u], v)
g[v] = append(g[v], u)
}
size := make([]int, n)
best := make([]int, n)
var dfs func(node, parent int)
dfs = func(node, parent int) {
size[node] = 1
maxPart := 0
for _, next := range g[node] {
if next == parent {
continue
}
dfs(next, node)
size[node] += size[next]
if size[next] > maxPart {
maxPart = size[next]
}
}
if n-size[node] > maxPart {
maxPart = n - size[node]
}
best[node] = maxPart
}
dfs(0, -1)
ans := 0
for i := 1; i < n; i++ {
if best[i] < best[ans] {
ans = i
}
}
return ans
}关键点
重心问题的核心是先算子树大小，再看“切开当前点后最大的那块有多大”。