复习 LCT 的时候才发现,这道题的数据有一点弱,如果你 pushdown 是这样写的:
void pushdown(int u){
if(!rev[u]) return;
swap(ch[u][0], ch[u][1]);
if(ch[u][0]) rev[ch[u][0]] ^= 1;
if(ch[u][1]) rev[ch[u][1]] ^= 1;
rev[u] = 0;
}
而与此同时你的 findroot 又是这样写的:
int findroot(int x){
access(x), splay(x);
while(ch[x][0]) pushdown(x), x = ch[x][0];
splay(x);
return x;
}
那就是错的,因为下穿标记之后 x 的左儿子可能并不存在而陷入死循环,却可以通过本题 。如果不改 pushdown 的话,findroot 正确的写法应为:
int findroot(int x){
access(x), splay(x);
for(;;){
pushdown(x);
if(!ch[x][0]) break;
x = ch[x][0];
}
splay(x);
return x;
}