关于 LCT 的一个小问题
  • 板块学术版
  • 楼主Plozia
  • 当前回复8
  • 已保存回复8
  • 发布时间2022/4/22 20:50
  • 上次更新2023/10/28 03:06:42
查看原帖
关于 LCT 的一个小问题
134000
Plozia楼主2022/4/22 20:50

rt,在 Cut(x, y) 中,一般的写法是这样的:

void Cut(int x, int y)
{
	MakeRoot(x);
	if (FindRoot(y) != x || fa(y) != x || Son(y, 0)) return ;
	fa(y) = 0; Son(x, 1) = 0; Update(x);
}

但是我自己想了一个新的方式,就是先 MakeRoot(x) 然后 Access(y),此时如果 x,yx,y 有连边那么 x,yx,y 应该有父子关系并且 y 是 x 的右儿子并且 y 没有左儿子,就是这样:

void Cut(int x, int y)
{
	MakeRoot(x); Access(y);
	if (fa(y) == x && Son(x, 1) == y && !Son(y, 0))
	{
		Son(x, 1) = fa(y) = 0; Update(x);
	}
}

将 Cut 改成这份代码之后,模板题 P3690 WA 了一个点,所以有人知道这个做法为什么错吗?还是说有什么别的地方没有考虑到?

保证别的函数是正确的(当然不排除别的函数有一点点小锅)。

2022/4/22 20:50
加载中...