改考试题的时候突然发现LCT压疯了写出来还挺好看?
好像写得比DC还短。。
namespace LinkCut_Tree{
int fa[NN],val[NN],sum[NN],tag[NN],son[NN][2];
bool get(int x){ return x==son[fa[x]][1]; }
bool isroot(int x){ return x!=son[fa[x]][0]&x!=son[fa[x]][1]; }
void rev(int x){ swap(son[x][0],son[x][1]); tag[x]^=1; }
void pushdown(int x){ if(tag[x]) rev(son[x][0]), rev(son[x][1]); tag[x]=0; }
void pushup(int x){ sum[x]=sum[son[x][0]]^sum[son[x][1]]^val[x]; }
void pushall(int x){ if(!isroot(x)) pushall(fa[x]); pushdown(x); }
void rotate(int x){
int y=fa[x],z=fa[y],xpos=get(x),ypos=get(y);
if(son[x][xpos^1]) fa[son[x][xpos^1]]=y; son[y][xpos]=son[x][xpos^1];
if(!isroot(y)) son[z][ypos]=x; fa[x]=z; son[x][xpos^1]=y; fa[y]=x;
pushup(y); pushup(x);
}
void splay(int x){ for(pushall(x);!isroot(x);rotate(x)) if(!isroot(fa[x])) rotate((get(x)^get(fa[x]))?x:fa[x]); }
void access(int x){ for(int y=0;x;x=fa[y=x]) splay(x), son[x][1]=y, pushup(x); }
int findroot(int x){ access(x); splay(x); while(son[x][0]) x=son[x][0]; splay(x); return x; }
void makeroot(int x){ access(x); splay(x); rev(x); }
void split(int x,int y){ makeroot(x); access(y); splay(y); }
void link(int x,int y){ makeroot(x); if(findroot(y)!=x) fa[x]=y; }
void cut(int x,int y){ makeroot(x); if(findroot(y)==x&&fa[y]==x&&!son[y][0]) fa[y]=son[x][1]=0; pushup(x); }
} using namespace LinkCut_Tree;
属实是在破事水