关于树剖的小问题
查看原帖
关于树剖的小问题
271736
Daidly楼主2021/11/13 13:41
void modify_l(int x,int y,int z){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		modify(1,n,dfn[top[x]],dfn[x],z,1);
		x=f[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	modify(1,n,dfn[x],dfn[y],z,1);
}

上面的代码是操作 11,也就是链加,默板子的时候,这里 if(dep[top[x]]<dep[top[y]])swap(x,y); 写成了 if(dep[x]<dep[y])swap(x,y); 后来发现错了(这样写只有 2020,其他全 CE)。

能解释一下为什么在向上跳的时候要选所在重链顶部深度进行比较吗(而不选点的深度)?

自己想了一下,感觉有点模糊(大概就是把 top[x] 看成 x 就变成了下面这样)。

while(x!=y){
	if(dep[x]<dep[y])swap(x,y);
	...
	x=f[x];
}

但还是不太能完全理解,所以发帖问一下。

2021/11/13 13:41
加载中...