明天就要月考了，总感觉现在这个时候还在做题不太好……呃，不过既然都已经开始做这题了，如果不AC了它的话，估计我也没有心情去月考了（好吧，我承认这一段是在胡扯233）

 

下面是正题：

这道题目的做法是块状树套上平衡树，我打的是Treap，感觉还是Treap好打一些，而且为了速度，我作死地打了指针+结构体，调试的时候真的是欲仙欲死。

首先，我们需要将整棵树分成好几个部分，至于怎么分块我就不说了，毕竟网上都应该能够搜到。分块之后，我们就将整棵树（我们定义其为1号树）变成了一棵很小的树，每一个结点都是一个块，我们定义这棵树为2号树。

0.查询

    查询的是一棵子树，首先，我们找到查询的结点u，接着，对u所属的那个块中的属于u子树的结点都查询一遍，判断其权值是不是严格大于x。其次，在2号树对1号树中u的子节点所属的块进行查询，因为每一个块都套上了Treap，查询的话还是挺方便的。具体的可以参照下图：

1.修改

    把点u的权值改成x，其实等于是在u所属块套上的Treap中，将u这个结点删去，改掉权值之后再将u插入回去，这里有一个坑点，我的Treap是根据每一块的根来算的，也就是说，有a1,a2..ak个结点都位于Treap[a1]中，那么将a1从Treap[a1]中删去之后再插入进去，最后得到的是一棵只有一个结点的Treap。

2.插入

    插入一个新结点要分类讨论，如果这个结点的父亲节点所属的块的大小还没有饱和，那么新插入的结点也属于这个块，否则，新插入的结点就是一个新的块，不要忘记将新的块所构成的新结点插入到2号树中。

3.删除

    删除操作也是一个麻烦事，我们假设u属于块pos[u]。如果pos[u]==u那么就在2号树中将这个结点和它的父亲结点断开就行了，否则，我们需要将u的所有子节点中属于pos[u]的点都从Treap[pos[u]]中删去然后再插入到新的Treap[pos[u]=u]中。其次，在2号树中，对于那些u子树所构成的块结点，需要将其和pos[u]断开连接，再重新和pos[u]=u连接。

 

大致就是这个样子，本来这个程序昨天中午就打好了的，调了大概一两个小时，直到后来，极限数据出错概率也只有5%~10%了，那才是最痛苦的时候，小数据大概对拍了半个多小时才拍出了一组数据将我的程序卡掉，结果扔到BZOJ上还是超时了，也不知道在哪里出了问题，直到不久前才发现，原来是对于块的size定义出了问题，为了调试方便，我把每块的大小都定义为了4 TAT。改成了400后就AC了，时间是五秒多，后来一直扩大这个数值，直到每块的size都在6000左右的时候，速度被我提到了1.75秒，感觉再进步就比较麻烦了。

另外，感觉这道题目的这种做法还是有点问题的，我发现如果是菊花图的话，似乎可以卡掉分块做法……不过我也懒得管这么多了，还是乖乖滚去复习月考吧……

 

Updata:BZOJ 3720 Gty的妹子树 和这道题目同一个出题人，操作比这题少了一个（断裂操作），其他都一样，所以你们都懂得。

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const int N=500010;
const int M=100010;
const int Q=200010;
const int size=6000;
struct Treap* null;
struct Treap{
    Treap *fa,*son[2];
    int key,data,sz;
    void newnode(int x) {
        data=x; key=rand(); sz=1;
        fa=son[0]=son[1]=null;
    }
    void updata() { sz=son[0]->sz+son[1]->sz+1;}
    void rotate() {
        Treap *x=this,*y=x->fa,*z=y->fa;
        int w=(y->son[0]==x);
        if (z!=null) z->son[z->son[1]==y]=x;
        x->fa=y->fa; y->fa=x;
        if (x->son[w]!=null) x->son[w]->fa=y;
        y->son[w^1]=x->son[w]; x->son[w]=y; 
        y->updata(); x->updata();
    }
    void insert(Treap *&y) {
        Treap *x=this; x->sz++;
        if (y->data>x->data) {
            if (x->son[1]!=null) x->son[1]->insert(y);
            else x->son[1]=y,y->fa=x;
            if (x->son[1]->key<x->key) x->son[1]->rotate();
        } else {
            if (x->son[0]!=null) x->son[0]->insert(y);
            else x->son[0]=y,y->fa=x;
            if (x->son[0]->key<x->key) x->son[0]->rotate();
        } x->updata();
    }
    Treap* merge(Treap *fat,Treap *x,Treap *y) {
        if (x==null&&y==null) return null;
        if (x==null) {
            y->fa=fat;
            return y;
        }
        if (y==null) {
            x->fa=fat;
            return x;
        }
        if (x->key<y->key) {
            x->son[1]=merge(x,x->son[1],y);
            x->fa=fat; x->updata();
            return x;
        } else {
            y->son[0]=merge(y,x,y->son[0]);
            y->fa=fat; y->updata();
            return y;
        }
    }
    void clear() {
        if (this==null) return;
        else this->updata();
        if (this->fa!=null) this->fa->clear();
    }
    void del() {
        Treap *x=this,*y=merge(x->fa,x->son[0],x->son[1]);
        x->fa->son[x->fa->son[1]==x]=y;
        x->fa->clear(); x->sz=1;
        x->fa=x->son[0]=x->son[1]=null;
    }
    int ask(int y) {
        if (this==null) return 0;
        Treap *x=this; int ans=0;
        if (x->data>y) ans++;
        if (y>=x->data) ans+=x->son[1]->ask(y);
        else {
            ans+=x->son[1]->sz;
            ans+=x->son[0]->ask(y);
        } return ans;
    }
    Treap* findroot() {
        if (this->fa==null) return this;
        else return this->fa->findroot();
    }
};
Treap pool[Q];
Treap* v[Q];
Treap* total;
int n,m,w[Q],lastans;
int pos[Q],sz[Q],fa[Q];
int g[Q],to[N],nxt[N],tot;
int G[Q],TO[N],NXT[N],TOT;
void read(int &a) {
    char ch; while (!((ch=getchar())>='0'&&ch<='9'));
    a=ch-'0'; while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
}
void addedge(int x,int y) {
    to[++tot]=y; nxt[tot]=g[x]; g[x]=tot;
    to[++tot]=x; nxt[tot]=g[y]; g[y]=tot;
}
void ADDEDGE(int x,int y) {
    TO[++TOT]=y; NXT[TOT]=G[x]; G[x]=TOT;
}
void init() {
    total=pool; null=total++;
    null->fa=null->son[0]=null->son[1]=null;
    null->key=null->data=null->sz=0;
}
void dfs(int x,int fat) {
    int cur=pos[x],k; fa[x]=fat;
    for (k=g[x];k;k=nxt[k]) if (to[k]!=fat) {
        if (sz[cur]+1<=size) {
            sz[pos[to[k]]=cur]++;
            Treap *t=v[cur]->findroot();
            t->insert(v[to[k]]);
        } else ADDEDGE(cur,pos[to[k]]);
        dfs(to[k],x);
    }
}
int query(int x,int y) {
    int k,ans=0; Treap *t;
    if (pos[x]==x) {
        t=v[x]->findroot();
        ans+=t->ask(y);
        for (k=G[x];k;k=NXT[k]) ans+=query(TO[k],y);
    } else {
        if (w[x]>y) ans++;
        for (k=g[x];k;k=nxt[k]) if (to[k]!=fa[x]&&fa[to[k]]==x) ans+=query(to[k],y);
    } return ans;
}
void change(int x,int y) {
    Treap *t; w[x]=y;
    t=v[x]->findroot();
    if (t==v[x]) {
        if (t->son[0]!=null) t=t->son[0];
        else if (t->son[1]!=null) t=t->son[1];
        else {
            v[x]->data=y;
            return;
        }
    }
    v[x]->del();
    t=t->findroot();
    v[x]->data=y;
    t->insert(v[x]);
}
void add(int fat,int x,int y) {
    v[x]=total++; fa[x]=fat;
    addedge(fat,x); w[x]=y;
    v[x]->newnode(y);
    if (sz[fat]+1<=size) {
        sz[pos[x]=pos[fat]]++;
        Treap *t=v[pos[fat]]->findroot();
        t->insert(v[x]);
    } else {
        sz[pos[x]=x]++;
        ADDEDGE(pos[fat],pos[x]);
    }
}
void delink(int X,int Y) {
    int K;
    if (TO[G[X]]==Y) G[X]=NXT[G[X]];
    else for (K=G[X];K;K=NXT[K]) {
        if (TO[NXT[K]]==Y) {
            NXT[K]=NXT[NXT[K]];
            return;
        }
    }
}
void cut(int x,int loc) {
    int k;
    if (pos[x]==x) delink(pos[fa[x]],x);
    else {
        v[x]->del(); sz[pos[x]]--;
        for (k=g[x];k;k=nxt[k]) {
            if (pos[to[k]]==pos[x]&&to[k]!=fa[x]&&fa[to[k]]==x) cut(to[k],loc);
            else if (to[k]!=fa[x]&&fa[to[k]]==x&&pos[to[k]]==to[k]) {
                delink(pos[loc],pos[to[k]]);
                ADDEDGE(loc,pos[to[k]]);
            }
        } sz[pos[x]=loc]++;
        if (pos[x]!=x) {
            Treap *t=v[loc]->findroot();
            t->insert(v[x]);
        }
    }
}
int main() {
    int i,x,y,k; init();
    for (read(n),i=1;i<n;i++) {
        read(x); read(y);
        addedge(x,y);
    }
    for (i=1;i<=n;i++) {
        read(w[i]); v[i]=total++;
        v[i]->newnode(w[i]);
        pos[i]=i;
    } dfs(1,0);
    for (read(m),i=1;i<=m;i++) {
        read(k); read(x); x^=lastans;
        if (k!=3) read(y),y^=lastans;
        if (k==0) printf("%d\n",lastans=query(x,y));
        else if (k==1) change(x,y);
        else if (k==2) add(x,++n,y);
        else if (k==3) if (fa[x]) cut(x,x),fa[x]=0;
    }
    return 0;
}