我曾在弦歌之中听过你，

檀板声碎，半出折子戏。

舞榭歌台被风吹去，

岁月深处尚有余音一缕……


Gty神(xian)犇(chong)从来不缺妹子……

他来到了一棵妹子树下，发现每个妹子有一个美丽度……

由于Gty很哲♂学，他只对美丽度大于某个值的妹子感兴趣。

他想知道某个子树中美丽度大于k的妹子个数。

某个妹子的美丽度可能发生变化……

树上可能会出现一只新的妹子……


维护一棵初始有n个节点的有根树(根节点为1)，树上节点编号为1-n，每个点有一个权值wi。

支持以下操作：

0 u x          询问以u为根的子树中，严格大于x的值的个数。(u^=lastans,x^=lastans)

1 u x          把u节点的权值改成x。(u^=lastans,x^=lastans)

2 u x          添加一个编号为"当前树中节点数+1"的节点，其父节点为u，其权值为x。(u^=lastans,x^=lastans)

最开始时lastans=0。

输入第一行包括一个正整数n(1<=n<=30000)，代表树上的初始节点数。

接下来n-1行，每行2个整数u,v，为树上的一条无向边。

任何时刻，树上的任何权值大于等于0，且两两不同。

接下来1行，包括n个整数wi，表示初始时每个节点的权值。

接下来1行，包括1个整数m(1<=m<=30000)，表示操作总数。

接下来m行，每行包括三个整数 op,u,v：

op,u,v的含义见题目描述。

保证题目涉及的所有数在int内。

对每个op=0，输出一行，包括一个整数，意义见题目描述。

By Autumn

#include<cstdio>#include<cmath>#include<vector>#include<algorithm>using namespace std;inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}const int N=6e4+5,M=N<<1;int n,m,last,size[N],sum,SIZE,w[N],top[N];struct node{    int v[M],next[M],head[M],tot;    bool del[M];    inline void add(int x,int y){        v[++tot]=y;next[tot]=head[x];head[x]=tot;    }}g,block,linked;vector<int>list[N];inline void init(int u,int f){    int root=top[u];    list[root].push_back(w[u]);    for(int i=g.head[u];i;i=g.next[i]){        if(g.v[i]==f){g.del[i]=1;continue;}         if(size[root]<SIZE)            size[root]++,top[g.v[i]]=root;        else            block.add(root,g.v[i]);        init(g.v[i],u);    }}inline void query_block(int u,int x){    sum+=list[u].end()-upper_bound(list[u].begin(),list[u].end(),x);    for(int i=block.head[u];i;i=block.next[i])        query_block(block.v[i],x);}inline void query_out_board(int u,int x){    if(w[u]>x) sum++;    for(int i=g.head[u];i;i=g.next[i]){        if(g.del[i]) continue;         if(top[u]==top[g.v[i]])            query_out_board(g.v[i],x);        else            query_block(g.v[i],x);    }}int main(){    #ifndef online_judge        freopen("gtygirltree.in","r",stdin);        freopen("gtygirltree.out","w",stdout);    #endif    n=read();    SIZE=(int)ceil(2.0*sqrt(n)*log2(n));    for(int i=1,x,y;i<n;i++){        x=read();y=read();        g.add(x,y);g.add(y,x);    }    for(int i=1;i<=n;i++) w[i]=read(),top[i]=i,size[i]=1;    init(1,0);    for(int i=1;i<=n;i++) if(top[i]==i) sort(list[i].begin(),list[i].end());    m=read(),last=0;    for(int opt,u,x,tp;m--;){        opt=read();u=read()^last;x=read()^last;        if(!opt){            sum=0;            if(u==top[u])                query_block(u,x);            else                query_out_board(u,x);            printf("%d\n",last=sum);        }        else if(opt==1){            tp=top[u];            list[tp].erase(lower_bound(list[tp].begin(),list[tp].end(),w[u]));            list[tp].insert(lower_bound(list[tp].begin(),list[tp].end(),x),x);            w[u]=x;        }        else{            w[++n]=x;            tp=top[u];            g.add(u,n);            if(size[tp]<SIZE){                top[n]=tp;                size[tp]++;                list[tp].insert(lower_bound(list[tp].begin(),list[tp].end(),x),x);            }            else{                top[n]=n;                size[u]=1;                list[n].push_back(x);                block.add(tp,n);            }        }    }    return 0;}