不知道什么情况,卡不过去
先发一个博客了
upd:块大小改了一下A了
#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include<cctype> #include<cstdio> #include<cstring> #include<iostream> char buf[(int)2e7],*vin=buf-1; #define getchar() (*++vin) int x,ch,flag; inline int read(){ flag=0; while(isspace(ch=getchar())); if(ch==45)ch=getchar(),flag=1; x=ch&15; while(isdigit(ch=getchar()))x=x*10+(ch&15); return flag?-x:x; } char bufo[(int)2e7],*vout=bufo-1; inline void pc(int x){*++vout=x;} inline void put(int x){ if(x>9)put(x/10); pc(x%10+48); } const int maxn = 100100; int n,m,t; const int bl = 256; const int bl4 = bl*4; struct block{ int tag,ad; short cnt[maxn<<2]; inline block(){tag=maxn<<1,memset(cnt,0,sizeof cnt),ad=0;} inline void ins(int x){++cnt[x+tag];} inline void del(int x){--cnt[x+tag];} inline void init(){for(int i=maxn*4-1;i--;)cnt[i]+=cnt[i+1];} inline void add(int x){++cnt[x+tag+1];} inline void dec(int x){--cnt[x+tag];} inline void alladd(){--tag,++ad;} inline void alldec(){++tag,--ad;} inline int query(){return cnt[tag+1];} }b[maxn/bl+1]; int a[maxn],c[maxn]; inline int getbit(int x){return a[x]+b[x/bl].ad;} inline int is_begin(int x){return x==1||x%bl==0;} inline int is_end(int x){return x==n||x%bl==bl-1;} inline int nxt_begin(int x){return x==1?bl:x+bl;} inline void add(int l,int r){ if(l / bl == r / bl){ for(;l<=r;++l)b[l/bl].add(getbit(l)),++a[l]; return ; } int L=std::max(l/bl*bl,1),R=l/bl*bl+bl-1; if(R-l >= l-L){ for(;--l>=L;)b[l/bl].dec(getbit(l)),--a[l]; b[L/bl].alladd(); }else for(;!is_begin(l);++l)b[l/bl].add(getbit(l)),++a[l]; l=R+1; for(;l+bl4<=r;l+=bl4){ b[l/bl].alladd(); b[l/bl+1].alladd(); b[l/bl+2].alladd(); b[l/bl+3].alladd(); } for(;l+bl<=r;l+=bl)b[l/bl].alladd(); L=l,R=std::min(L+bl-1,n); if(r-L >= R-r){ for(;++r<=R;)b[r/bl].dec(getbit(r)),--a[r]; b[L/bl].alladd(); }else for(;l<=r;++l)b[l/bl].add(getbit(l)),++a[l]; } inline void dec(int l,int r){ if(l / bl == r / bl){ for(;l<=r;++l)b[l/bl].dec(getbit(l)),--a[l]; return ; } int L=std::max(l/bl*bl,1),R=l/bl*bl+bl-1; if(R-l >= l-L){ for(;--l>=L;)b[l/bl].add(getbit(l)),++a[l]; b[L/bl].alldec(); }else for(;!is_begin(l);++l)b[l/bl].dec(getbit(l)),--a[l]; l=R+1; for(;l+bl4<=r;l+=bl4){ b[l/bl].alldec(); b[l/bl+1].alldec(); b[l/bl+2].alldec(); b[l/bl+3].alldec(); } for(;l+bl<=r;l+=bl)b[l/bl].alldec(); L=l,R=std::min(L+bl-1,n); if(r-L >= R-r){ for(;++r<=R;)b[r/bl].add(getbit(r)),++a[r]; b[L/bl].alldec(); }else for(;l<=r;++l)b[l/bl].dec(getbit(l)),--a[l]; } inline int query(int l,int r){ int ans=0; if(l/bl==r/bl){ for(;l<=r;++l)ans+=getbit(l)>0; return ans; } int L=std::max(l/bl*bl,1),R=l/bl*bl+bl-1; if(R-l >= l-L){ for(;--l>=L;)ans-=getbit(l)>0; ans+=b[L/bl].query(); }else for(;l <= R;++l)ans+=getbit(l)>0; l=R+1; for(;l+bl4<=r;l+=bl4){ ans+=b[l/bl].query(); ans+=b[l/bl+1].query(); ans+=b[l/bl+2].query(); ans+=b[l/bl+3].query(); } for(;l+bl<=r;l+=bl)ans+=b[l/bl].query(); L=l,R=std::min(L+bl-1,n); if(r-L >= R-r){ for(;++r<=R;)ans-=getbit(r)>0; ans+=b[L/bl].query(); }else for(;l<=r;++l)ans+=getbit(l)>0; return ans; } struct T{ int to,nxt; }way[maxn<<1]; int h[maxn],num; inline void adde(int x,int y){ way[++num]={y,h[x]},h[x]=num; way[++num]={x,h[y]},h[y]=num; } int size[maxn],dfn[maxn],fa[maxn],dep[maxn],vis[maxn],top[maxn],idx; inline void build(){ for(int i=1;i<=n;++i)a[dfn[i]]=c[i]; for(int i=1;i<=n;++i)b[i/bl].ins(a[i]); for(int i=0;i<=n/bl;++i)b[i].init(); } inline void dfs(int x){ size[x]=vis[x]=1,dep[x]=dep[fa[x]]+1; for(int i=h[x];i;i=way[i].nxt) if(!vis[way[i].to])fa[way[i].to]=x,dfs(way[i].to),size[x]+=size[way[i].to]; vis[x]=0; } inline void dfs(int x,int top){ vis[x]=1,dfn[x]=++idx,::top[x]=top; int ms=0; for(int i=h[x];i;i=way[i].nxt)if(!vis[way[i].to]&&size[way[i].to]>size[ms])ms=way[i].to; if(ms)dfs(ms,top); for(int i=h[x];i;i=way[i].nxt)if(!vis[way[i].to]&&way[i].to!=ms)dfs(way[i].to,way[i].to); vis[x]=0; } inline void modify(int x,int y,int v){ while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])std::swap(x,y); (v==1?add:dec)(dfn[top[x]],dfn[x]),x=fa[top[x]]; } (v==1?add:dec)(std::min(dfn[x],dfn[y]),std::max(dfn[x],dfn[y])); } inline int Query(int x,int y){ int ans=0; while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])std::swap(x,y); ans+=query(dfn[top[x]],dfn[x]),x=fa[top[x]]; } ans+=query(std::min(dfn[x],dfn[y]),std::max(dfn[x],dfn[y])); return ans; } inline int Query(int x){return query(dfn[x],dfn[x]+size[x]-1);} int main(){ fread(buf,1,sizeof buf,stdin); n=read(),m=read(),t=read()==1; for(int i=1;i<n;++i)adde(read(),read()); for(int i=1;i<=n;++i){ c[i]=read(); if(c[i] > 100000)c[i]=100001; if(c[i] < -100000)c[i]=-100001; } dfs(1),dfs(1,1),build(); for(int i=1,l=0;i<=m;++i){ int x,y,w,opt; opt=read(); if(opt==1) x=read(),y=read(),w=read(),modify(x^l,y^l,w); if(opt==2) x=read(),y=read(),put(l=Query(x^l,y^l)),pc(10); if(opt==3) x=read(),put(l=Query(x^l)),pc(10); l *= t; } fwrite(bufo,vout-bufo+1,1,stdout); }