关于点分治为什么可以这样实现?
  • 板块学术版
  • 楼主hhhqx
  • 当前回复2
  • 已保存回复3
  • 发布时间2024/12/11 08:27
  • 上次更新2024/12/11 17:10:55
查看原帖
关于点分治为什么可以这样实现?
736787
hhhqx楼主2024/12/11 08:27

在求重心的时候,还需要 mx[x] = max(mx[x], sum - sz[x])

sum 的取值在题解里都是直接 sum = sz[nxt], Get_root(nxt, 0),但是如果 nxt 在求重心时是 x 的父亲,那 sum 的取值不就不对了吗?

或者说这样还可以保证复杂度?

2024/12/11 08:27
加载中...