关于点分治的size数组
查看原帖
关于点分治的size数组
371968
ningago寄寄人楼主2022/6/7 17:48

RT。请看下面代码的注释部分:

void solve(int k)
{
	vis[k] = 1;
	calc(k);
	for(int i = h[k];~i;i = ne[i])
	{
		int nx = e[i];
		if(vis[nx])
			continue;
		root = 0;
		get_root(nx,0,sz[nx]);//"3"
		solve(root);
	}
}

int main()
{
	memset(h,-1,sizeof(h));
	scanf("%d%d",&n,&m);
	for(int i = 1,x,y,z;i < n;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
	}
	for(int i = 1;i <= m;i++)
		scanf("%d",&q[i]);
	maxp[0] = n;
	get_root(1,0,n);//"1"
	get_root(root,0,n);//"2"
	solve(root);
	for(int i = 1;i <= m;i++)
		printf("%s\n",ok[i] ? "AYE" : "NAY");
	return 0;
}

在许多的题解中 "2" 这行是不需要加的。但根据Agoh大佬在B站的说法,"1"中算出的sz是以节点 11 为根的子树大小,会影响"3"带来的复杂度,所以加上"2"算出"sz"的就是以 rootroot 为根的大小。

然后……运行时间还多了5ms……

所以有没有必要加上"2"呢?

2022/6/7 17:48
加载中...