Lvat_s Blog

虽然已经有官方题解了而且写的和我一样……但是我还来写一次题解凑文章数

首先看了一下题目，发现不会做，就去看题解。

题解中说:"用LCT统计子树异或和"，我不会啊！

找到myy代码仔细看了一遍，大概也会统计子树异或和了。

首先我们考虑正常的LCT,你直接把两个child的和异或起来的和其实是你Access的那条链上的和。

那么统计子树就要从这里入手。

我们在Access时加上一些操作:如果原先选中的链不为Null,异或之；如果当前的选中的节点不为Null,异或之；

这样为什么就可以统计子树了呢？

（注意题目的性质，我们的子树异或和一定是Access访问过这个子树的全部节点，所以才能这么做）

考虑一开始啥都没有。

然后我们选中了一条链，那么原先的链啥也没有，我们在Pushup的时候就不考虑异或。

但是现在选中的链是存在的，我们异或一下。

那么我们就统计了这一条链。

之后同理

至于为什么要异或s_c，那是因为你在选中时统计了这个，之后Pushup时s_t又统计了一次

所以要还原

然后我们这题可以随机赋权值，每次碰到就异或一下，求解时确认这条边是否唯一存在即可。

代码跑得并不快(6097ms)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=500005;

int n,m,ID,ans,h[N],en,fa[N],val[N],cnt;
pair<int,int> path[N];

inline void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

inline int Abs(const int &x){return x>0?x:-x;}

inline int Rand(){
return (rand()<<16)|rand();
}

struct Edge{
int b,next;
}e[N<<1];

inline void AddEdge(const int &sa,const int &sb){e[++en].b=sb;e[en].next=h[sa];h[sa]=en;}

struct Node{
int v,v_t,s_c,s_t;
bool rev;
Node *ch[2],*fa;
Node();
inline void Pushdown();
inline void Pushup();
}*tree[N],*Null;

Node::Node(){v=v_t=s_c=s_t=rev=0;ch[0]=ch[1]=fa=Null;}

inline void Node::Pushdown(){
if(rev){
    if(ch[0]!=Null)ch[0]->rev^=1;
    if(ch[1]!=Null)ch[1]->rev^=1;
    swap(ch[0]->ch[0],ch[0]->ch[1]);
    swap(ch[1]->ch[0],ch[1]->ch[1]);
	rev=0;
}
}

inline void Node::Pushup(){
s_t=v_t;s_c=v;
if(ch[0]!=Null)s_t^=ch[0]->s_t,s_c^=ch[0]->s_c;
if(ch[1]!=Null)s_t^=ch[1]->s_t,s_c^=ch[1]->s_c;
}

Node *GetNull(){Node *p=new Node();p->fa=p->ch[0]=p->ch[1]=p;return p;}
int Notroot(Node *x){return x->fa->ch[0]==x||x->fa->ch[1]==x;}
void Prepare(Node *x){if(Notroot(x))Prepare(x->fa);x->Pushdown();}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(Notroot(y))z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}

void Splay(Node *x){
Prepare(x);
while(Notroot(x)){
	Node *y=x->fa,*z=y->fa;
	if(!Notroot(y))Rotate(x,y->ch[0]==x);
    else {
        if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
		else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
		else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
		else {Rotate(y,0);Rotate(x,0);}
    }
}
}

void Access(Node *x){
for(Node *y=Null;x!=Null;y=x,x=x->fa){
	Splay(x);
	if(x->ch[1]!=Null)x->v_t^=x->ch[1]->s_t^x->ch[1]->s_c;
	if(y!=Null)x->v_t^=y->s_t^y->s_c;
	x->ch[1]=y;
    x->Pushup();
}
}

inline void Makeroot(Node *x){
Access(x);
Splay(x);
x->rev^=1;
swap(x->ch[0],x->ch[1]);
}

inline void Link(Node *x,Node *y){
Makeroot(x);
Access(y);
Splay(y);
y->v_t^=x->s_t^x->s_c;
x->fa=y;
Access(x);
}

inline void Cut(Node *x,Node *y){
Makeroot(x);
Access(y);
Splay(y);
x->fa=Null;
y->ch[0]=Null;
x->Pushup();
}

inline void Change(Node *x,int y){Access(x);Splay(x);x->v^=y;x->Pushup();}
inline bool Query(Node *x,Node *y){Makeroot(x);Access(y);Splay(y);/*printf("DEBUG_Q: %d %d %d %d\n",y->v,y->v_t,y->v^y->v_t,ans);*/return (y->v^y->v_t)==ans;}
inline void dfs(int u){for(int i=h[u];i;i=e[i].next){int v=e[i].b;if(v==fa[u])continue;fa[v]=u;dfs(v);}}

int main(){
freopen("207.in","r",stdin);
freopen("207.out","w",stdout);
Read(ID);Read(n);Read(m);
if(ID==11){puts("OrzOrzOrz\nHello,world!\n233666");return 0;}
Null=GetNull();
for(int i=1;i<n;i++){
	int u,v;
    Read(u);Read(v);
	AddEdge(u,v);AddEdge(v,u);
}
dfs(1);
for(int i=1;i<=n;i++)tree[i]=new Node();
for(int i=2;i<=n;i++)tree[i]->fa=tree[fa[i]];
for(int i=0;i<m;i++){
	int opt,u,v,x,y;
    Read(opt);
    if(opt==1){Read(u);Read(v);Read(x);Read(y);Cut(tree[u],tree[v]);Link(tree[x],tree[y]);}
    if(opt==2){Read(x);Read(y);int tp=Rand();ans^=tp;Change(tree[x],tp);Change(tree[y],tp);path[++cnt]=make_pair(x,y);val[cnt]=tp;}
    if(opt==3){Read(x);Change(tree[path[x].first],val[x]);Change(tree[path[x].second],val[x]);ans^=val[x];}
    if(opt==4){Read(x);Read(y);puts(Query(tree[x],tree[y])?"YES":"NO");}
}
return 0;
}