这是AC程序:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct LCT{
int fa,son[2],tag;
}t[N];
inline int which(int x){return x == t[t[x].fa].son[1];}
inline bool isroot(int x){return x != t[t[x].fa].son[0] && x != t[t[x].fa].son[1];}
inline void rever(int x){if(!x) return; swap(t[x].son[0],t[x].son[1]); t[x].tag ^= 1;}
inline void pushdown(int x){if(!t[x].tag) return; rever(t[x].son[0]);rever(t[x].son[1]);t[x].tag = 0;}
inline void rorate(int x)
{
int dir = which(x),y = t[x].fa,z = t[y].fa;
t[y].son[dir] = t[x].son[dir ^ 1];
if(t[x].son[dir ^ 1]) t[t[x].son[dir ^ 1]].fa = y;
if(!isroot(y)) t[z].son[which(y)] = x;
t[x].fa = z;
t[x].son[dir ^ 1] = y;
t[y].fa = x;
}
inline void splay(int x)
{
int st[N],top = 0,now = x;
while(!isroot(now)) st[++top] = now,now = t[now].fa; st[++top] = now;
while(top) pushdown(st[top]),top--;
while(!isroot(x))
{
if(!isroot(t[x].fa))
rorate((which(x) ^ which(t[x].fa)) ? x : t[x].fa);
rorate(x);
}
}
inline void access(int x)
{
for(int rc = 0;x;rc = x,x = t[x].fa)
splay(x),t[x].son[1] = rc;
}
inline int findroot(int x)
{
access(x);splay(x);
while(t[x].son[0]) pushdown(x),x = t[x].son[0];
splay(x);// 注意这里
return x;
}
inline void makeroot(int x)
{
access(x);splay(x);rever(x);
}
inline void link(int x,int y)
{
makeroot(x);
if(findroot(y) == x) return;
t[x].fa = y;
}
inline void cut(int x,int y)
{
makeroot(x);
if(findroot(y) != x || t[y].fa != x || t[y].son[0]) return;
t[y].fa = 0;t[x].son[1] = 0;
}
int main()
{
int n,m;
cin>>n>>m;
string op;int x,y;
for(int i = 1;i <= m;i++)
{
cin>>op>>x>>y;
if(op == "Connect") link(x,y);
if(op == "Destroy") cut(x,y);
if(op == "Query") cout<<(findroot(x) == findroot(y) ? "Yes" : "No")<<endl;
}
return 0;
}
中间LCT找原来树上的根的地方是这样写的:
inline int findroot(int x)
{
access(x);splay(x);
while(t[x].son[0]) pushdown(x),x = t[x].son[0];
splay(x);// 注意这里
return x;
}
那个注释掉的地方理论上来说是用来调节时间复杂度的,但是删掉后第一个样例无法通过。这是为什么?