求助,关于文章《一种基于错误的寻找重心方法的点分治的复杂度分析》
  • 板块学术版
  • 楼主Edgebright
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/6/8 11:42
  • 上次更新2023/10/23 13:40:54
查看原帖
求助,关于文章《一种基于错误的寻找重心方法的点分治的复杂度分析》
762588
Edgebright楼主2023/6/8 11:42

一种基于错误的寻找重心方法的点分治的复杂度分析

蒟蒻最近学习淀粉质,关于这些方法有一些疑惑,逻辑也不太清晰,见谅。

大佬在这里面说,“可以明显发现,当 KK 和 K′K' 处于上一层重心 OO 的同一子树时,传入的点数是错误的。”这句话是什么意思?以及,在大佬说的“法1”,以第一个所有子树大小不超过 n2\frac{n}{2} 的为重心时,是否包含子树大小的更新?如下:

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;
}

如果本身没有包含这一步的话,加上这一步能否使这种方式正确?

2023/6/8 11:42
加载中...