关于重链剖分
  • 板块学术版
  • 楼主WZKQWQ
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/10/27 21:28
  • 上次更新2023/10/27 05:32:01
查看原帖
关于重链剖分
239433
WZKQWQ楼主2022/10/27 21:28

Rt,在写重链剖分的时候如果我使重链长度大于n\sqrt n使裂开为什么会WA?

void dfs(int x,int y){
	top[x] = y;
	dfn[x] = ++tot;
	//add(1,1,n,tot,a[x]);
	add(head[y],Log,a[x]);
	if(son[x]){
		//if(d[x] - d[y] <= Q) dfs(son[x],y);
		//else dfs(son[x],son[x]);这里,下面就AC了
		dfs(son[x],y);
	} 
	for(int to:e[x]) if(to != fa[x] && to != son[x]) dfs(to,to);
	R[x] = tot;
}

然后是求处理链上的代码:

int find(int x,int y,int z){
	int tx = top[x],ty = top[y],fx = 1,fy = 1,mx = 0;
	while(tx != ty){
		if(d[tx] > d[ty]){
			if(fx){
				mx = max(mx,get(x,tx,z));
				fx = 0;
			} else mx = max(mx,ask(head[tx],Log,z));
			x = fa[tx];
		} else {
			if(fy){
				mx = max(mx,get(y,ty,z));
				fy = 0;
			} else mx = max(mx,ask(head[ty],Log,z));
			y = fa[ty];
		}
		tx = top[x],ty = top[y];
	}
	if(d[x] < d[y]) swap(x,y);
	mx = max(mx,get(x,y,z));
	return mx;
}
2022/10/27 21:28
加载中...