一种基于错误的寻找重心方法的点分治的复杂度分析
蒟蒻最近学习淀粉质,关于这些方法有一些疑惑,逻辑也不太清晰,见谅。
大佬在这里面说,“可以明显发现,当 K 和 K′ 处于上一层重心 O 的同一子树时,传入的点数是错误的。”这句话是什么意思?以及,在大佬说的“法1”,以第一个所有子树大小不超过 2n 的为重心时,是否包含子树大小的更新?如下:
void centroid(int u, int fa)
{
int mxsub = 0;
sz[u] = 1;
for(int i = h[u]; i; i = e[i].n)
{
int to = e[i].t;
if(vis[to] || to == fa)continue;
centroid(to, u);
if(ctr)return;
sz[u] += sz[to];
mxsub = max(mxsub, sz[to]);
}
mxsub = max(mxsub, num - sz[u]);
if(mxsub <= num/2)
{
ctr = u;
printf("Ctr%lld\n",ctr);
sz[fa] = num - sz[u];
}
return;
}
如果本身没有包含这一步的话,加上这一步能否使这种方式正确?