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,y 有连边那么 x,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 了一个点,所以有人知道这个做法为什么错吗?还是说有什么别的地方没有考虑到?
保证别的函数是正确的(当然不排除别的函数有一点点小锅)。