社区讨论
关于寻找重心时当前层总节点数量的疑问
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)
CPPvoid 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 条回复,欢迎继续交流。
正在加载回复...