Lvat_s Blog

我是纸张……

自以为考虑到所有的情况了，但是却在2操作后忘记给主树加边了……

55555555555555……

-----------

这题虽然可以用高明的数据结构做但是也可以用块状树写。我写的就是块状树

把树分成若干块，父节点的块大小没到要求就加到父节点的块里面去。

这样貌似会被星形的数据卡掉但是既然过了也就不管了

定义原来的树为主树

对于块和块之间连接形成的树称为辅树

加点时一定要在辅树和主树中都更新！

然后对于辅树的每个节点维护一个数据结构(我用了vector,实际上可以是treap等平衡树而且效果肯定更好)

先把本块内的数据查询完然后往下直接走整块

就行了

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

const int N=60005,block_size=200;

int n,lastans,m,en,h[N],w[N],belong[N],block_num,fa[N],bh[N];

struct Edge{int b,next;}e[N<<1];
inline void AddEdge(int sa,int sb){e[++en].b=sb;e[en].next=h[sa];h[sa]=en;}
inline void AddBkEg(int sa,int sb){e[++en].b=sb;e[en].next=bh[sa];bh[sa]=en;}

struct Node{
vector<int> Vx;int siz;
Node(){siz=0;}
inline void Insert(int x){if(!siz)Vx.push_back(x);else Vx.insert(upper_bound(Vx.begin(),Vx.end(),x),x);siz++;}
inline void Change(int x,int y){Vx.erase(lower_bound(Vx.begin(),Vx.end(),x));Insert(y);}
inline int Query(int x){return Vx.end()-upper_bound(Vx.begin(),Vx.end(),x);}
}block[N];

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

void dfsp(int u,int fat){
if(block[belong[fat]].siz<block_size)belong[u]=belong[fat];
else belong[u]=++block_num,AddBkEg(belong[fat],belong[u]);
block[belong[u]].Insert(w[u]);
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	if(v==fat)continue;
	fa[v]=u;
	dfsp(v,u);
}
}

void dfsb(int u,int x){
lastans+=block[u].Query(x);
for(int i=bh[u];i;i=e[i].next)dfsb(e[i].b,x);
}

void dfss(int u,int x){
if(w[u]>x)lastans++;
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
    if(v==fa[u])continue;
    if(belong[v]==belong[u])dfss(v,x);
    else dfsb(belong[v],x);
}
}

int main(){
freopen("3720.in","r",stdin);
freopen("3720.out","w",stdout);
Read(n);
for(register int i=1;i<n;i++){int u,v;Read(u);Read(v);AddEdge(u,v);AddEdge(v,u);}
for(register int i=1;i<=n;i++)Read(w[i]);
dfsp(1,0);
Read(m);
while(m--){
    int opt,u,v;
    Read(opt);Read(u);Read(v);
    u^=lastans;v^=lastans;
    if(opt==0){lastans=0;dfss(u,v);printf("%d\n",lastans);}
    if(opt==1){block[belong[u]].Change(w[u],v);w[u]=v;}
    if(opt==2){w[++n]=v;AddEdge(u,n);if(block[belong[u]].siz<block_size)belong[n]=belong[u];else belong[n]=++block_num,AddBkEg(belong[u],belong[n]);block[belong[n]].Insert(v);fa[n]=u;}
}
return 0;
}