社区讨论

关于寻找重心时当前层总节点数量的疑问

P3806【模板】点分治参与者 3已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@mm5moq6c
此快照首次捕获于
2026/02/28 09:14
上周
此快照最后确认于
2026/03/01 21:25
上周
查看原帖
CPP
void fdrt(int u,int fa){
    siz[u]=1;maxp[u]=0;
    for(auto& [v,w]:e[u]){
        if(v==fa||vis[v])continue;
        fdrt(v,u);
        siz[u]+=siz[v];
        maxp[u]=max(maxp[u],siz[v]);
    }
    maxp[u]=max(maxp[u],sump-siz[u]);
    if(maxp[u]<maxp[root])root=u;
}
这是我的找重心代码,可以看到他需要知道当前层总节点数量(sump)
CPP
void cdt(int u){
    vis[u]=1;calc(u);
    for(auto& [v,w]:e[u]){
        if(vis[v])continue;
        root=0;
        sump=siz[v];
        fdrt(v,0);
        cdt(root);
    }
}
void CDT(){
    maxp[0]=1e9;
    root=0;
    sump=n;
    fdrt(1,0);
    cdt(root);
}
这是我的淀粉质代码(已AC),他第一次将sump设为n,然后每次将sump设为以上一层重心的子节点为根当前节点的子树大小(没有上一层就是1号节点),我今天再看感觉有点问题,但是当时我是跟着tj写的,有几篇tj也是这么写的,所以说这个写法时对的吗?

回复

7 条回复,欢迎继续交流。

正在加载回复...