关于树的重心
  • 板块灌水区
  • 楼主luogu_mengxin
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/20 09:29
  • 上次更新2024/8/20 09:33:31
查看原帖
关于树的重心
579970
luogu_mengxin楼主2024/8/20 09:29

为啥点分治的重心写成这样?

每次获取重心后,更新父亲结点的 size?

void getroot(int u, int fa) {
    int mxs = 0;
    sz[u] = 1;
    for (int i = head[u]; i; i = e[i].next) {
        int to = e[i].to;
        if (to == fa || del[to]) continue;
        getroot(to, u);
        if (root != -1) return;
        sz[u] += sz[to];
        mxs = max(mxs, sz[to]);
    }
    mxs = max(mxs, sum - sz[u]);
    if (mxs * 2 <= sum) {
        root = u;
        sz[fa] = sum - sz[u];
    }
}
2024/8/20 09:29
加载中...