在求重心的时候,还需要 mx[x] = max(mx[x], sum - sz[x])。
mx[x] = max(mx[x], sum - sz[x])
sum 的取值在题解里都是直接 sum = sz[nxt], Get_root(nxt, 0),但是如果 nxt 在求重心时是 x 的父亲,那 sum 的取值不就不对了吗?
sum
sum = sz[nxt], Get_root(nxt, 0)
nxt
x
或者说这样还可以保证复杂度?