BZOJ_3282_Tree_(LCT)

描述

---

http://www.lydsy.com/JudgeOnline/problem.php?id=3282

给出n个点以及权值,四种操作:

0.求x,y路径上的点权值的异或和.

1.连接x,y.

2.断开x,y.

3.将x的权值改为t.

分析

---

LCT模板题.

说几点自己的感悟和需要注意的地方吧(这里把原来的树称作树,平衡树称作Splay以避免混淆):

1.LCT是用Splay来维护一个森林(通过将链剖分),Splay以深度为关键字,即深度小的在左边,深度大的在右边.森林中每一棵树都有一个或多个Splay,刚开始的时候每个点都是一个独立的Splay.如果两个点x,y相连,假设x的深度小,则我们把y->pa设为x,但是注意并不把x的孩子设为y.这样一棵树中,还是每个点都是一个单独的Splay,不过与普通的Splay不同的是,这里的Splay的根并不一定上面连着null,而是它的父亲节点不连着它.

2.Access操作是LCT的最基本也是最重要的操作,它的作用是:如果我们Access(x),那么就会将x所在树的根节点到x的路径上的所有点放进一个Splay中.这样进行多次Access的话,一棵树就被分成了许多个Splay且每个Splay可能不再只代表一个点(可以自己画图看看).对于Splay的根节点,它的pa代表的是这个Splay(是一条链)的树上的祖先,而对于非Splay节点,它的父亲就是它在Splay中的父亲.这样我们就有了一个判断Splay根节点的方法:看它的pa是否连着它,如果连着,则这个点不是Splay的根,如果不连着,那么这个点就是Splay的根.当然,树的根节点就是父亲为null的点了.

另外注意Access(x)之后一定要Splay(x),(原来的x).原因如下(看不懂的先跳过去看下面的):

(1).在Access操作的时候,每次在树中深度小的Splay链上挂上深度大的点,都是挂在右孩子,但是都没有进行push_up()操作,所以之后进行一次Splay(x),x沿着右边转上去的过程中就把所有没有push_up的点都push_up了.(当然也可以在Access函数中每一步都push_up(),但好像会慢一点)

(2).保证在make_root(x)之后x同时也是Splay的根,这样在link函数里面make_root(x)之后才能直接x->pa=y.

(3).Access(x)之后无论进行什么有关x所在Splay的操作都要先对Splay中的某个点进行splay操作,x点在Splay的根节点的话,因为有fix函数,所以x位置的标记一定会传下去.如果我们make_root(x)过了的话,这样保证了x是最左边的也就是深度最小的,这样find_root函数才能找到正确树的根.

3.make_root操作.make_root(x)之后,x就是树的根了(有向树无此操作).我们思考会发现,对于树原来的根y和现在要成为根的x,我们只需要将y到x路径上的所有点的深度倒过来就可以了.所以我们Access(x),splay(x),x->rev^=true(将代表y到x这条链的Splay中的所有点深度倒转)即可.

4.link操作.make_root(x),然后直接连就行了(make_root的时候在Access之后进行了splay,所以x一定是Splay的根,所以可以直接连).

5.cut操作.make_root(x),Access(y),Splay(y)这样这个Splay中就只有x,y两个点,且x是y的左儿子,然后x->pa=null,y->ch[0]=null即可.

6.fix函数的重要性.一般的Splay在进行splay操作的时候可以边转边向下传标记(rev).但是LCT中的Splay是时时刻刻在变的,可能一会之后Splay中就不再是原来那些点了(多了一些新的,少了一些以前的).如果我们边转边传标记的话,会导致Splay中上面的标记没有完全传下来,一会如果下面的点换了(原来的点没了,新增了别的点),这个标记就出问题了.所以我们Splay操作的时候要先找到Splay的根,然后从上到下(直到要进行splay操作的点x),把标记全部放下来,这样保证了所有会影响x的子节点的标记都放干净了.因为每次Splay换点的时候都是先splay(x),再把x->ch[1]换掉,所以我们每次splay(x)的时候把会影响x子节点的标记都处理好,再换x的子节点,就不会有问题了.

7.因为Access之后一定要进行splay操作,所以我以后直接把splay写在Access函数里面了.

8.其实我觉得我讲的一点也不清楚...

#include <bits/stdc++.h>
using namespace std;

const int maxn=300000+5;
int n,m;
struct node{
    int v,s; bool rev;
    node* ch[2],* pa;
    node(int v,node* t):v(v),s(0),rev(false){ ch[0]=ch[1]=pa=t; }
    bool d(){ return pa->ch[1]==this; }
    bool c(){ return pa->ch[0]==this||pa->ch[1]==this; }//判断这个点有没有被父亲连着.
    void setc(node* t,bool d){ ch[d]=t; t->pa=this; }
    void push_up(){ s=ch[0]->s^ch[1]->s^v; }
    void push_down(){
        if(rev){
            ch[0]->rev^=true;
            ch[1]->rev^=true;
            swap(ch[0],ch[1]);
            rev=false;
        }
    }
}* t[maxn],* null;
void rot(node* o){
    node* pa=o->pa; bool d=o->d();
    pa->push_down(); o->push_down();
    if(pa->c()) pa->pa->setc(o,pa->d());
    else o->pa=pa->pa;
    pa->setc(o->ch[!d],d);
    o->setc(pa,!d);
    pa->push_up();
}
void fix(node* o){
    if(o->c()) fix(o->pa);
    o->push_down();
}
void splay(node* o){
    fix(o);//必须要找到根再放标记,否则标记下放不完全,splay又是动态的,会出错.
    while(o->c())
        if(!o->pa->c()) rot(o);
        else o->d()==o->pa->d()?(rot(o->pa),rot(o)):(rot(o),rot(o));
    o->push_up();
}
void access(node* x){//access之后一定要splay原来的x
    node *y=null;
    for(;x!=null;y=x, x=x->pa){
        splay(x);
        x->ch[1]=y;
    }
}
void make_root(node* o){
    access(o);
    splay(o);
    o->rev^=true;
}
void link(node *u,node *v){
    make_root(u);
    u->pa=v;
}
void cut(node* u,node *v){
    make_root(u);
    access(v);
    splay(v);
    u->pa=null;
    v->ch[0]=null;
}
node* find_root(node* o){
    access(o);
    splay(o);
    while(o->ch[0]!=null) o=o->ch[0];
    return o;
}
int query(node *u,node *v){
    make_root(u);
    access(v);
    splay(v);
    return v->s;
}
void change(node *x,int y){
    splay(x);
    x->v=y;
    x->push_up();
}
int main(){
    null=new node(0,NULL);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int x; scanf("%d",&x);
        t[i]=new node(x,null);
    }
    for(int i=1;i<=m;i++){
        int c,x,y;
        scanf("%d%d%d",&c,&x,&y);
        if(c==0) printf("%d
",query(t[x],t[y]));
        else if(c==1){ if(find_root(t[x])!=find_root(t[y])) link(t[x],t[y]); }
        else if(c==2){ if(find_root(t[x])==find_root(t[y])) cut(t[x],t[y]); }
        else if(c==3) change(t[x],y);
    }
    return 0;
}

3282: Tree

Time Limit: 30 Sec  Memory Limit: 512 MB
Submit: 1417  Solved: 615
[Submit][Status][Discuss]

Description

给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。

０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证ｘ到ｙ是联通的。

１：后接两个整数（ｘ，ｙ），代表连接ｘ到ｙ，若ｘ到Ｙ已经联通则无需连接。

２：后接两个整数（ｘ，ｙ），代表删除边（ｘ，ｙ），不保证边（ｘ，ｙ）存在。

３：后接两个整数（ｘ，ｙ），代表将点Ｘ上的权值变成Ｙ。

 

Input

第１行两个整数，分别为Ｎ和Ｍ，代表点数和操作数。

第２行到第Ｎ＋１行，每行一个整数，整数在［１，１０＾９］内，代表每个点的权值。

第Ｎ＋２行到第Ｎ＋Ｍ＋１行，每行三个整数，分别代表操作类型和操作所需的量。

 

 

 

Output

对于每一个０号操作，你须输出Ｘ到Ｙ的路径上点权的Ｘｏｒ和。

Sample Input

3 3
1
2
3
1 1 2
0 1 2
0 1 1

Sample Output

3
1

HINT

１＜＝Ｎ，Ｍ＜＝３０００００

Source

动态树