【BZOJ 1146】[CTSC2008]网络管理Network

#include <cstdio>#include <cstring>#include <algorithm>#define mid ((l+r)>>1)#define newnode (node+(sz++))const int N=80010;const int Inf=99999999;char xB[(1<<15)+10],*xS=xB,*xTT=xB;#define gtc() (xS==xTT&&(xTT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xTT)?0:*xS++)inline void read(int &sum){ ???register char ch=gtc(); ???for(sum=0;ch<‘0‘||ch>‘9‘;ch=gtc()); ???for(;ch>=‘0‘&&ch<=‘9‘;sum=(sum<<1)+(sum<<3)+ch-‘0‘,ch=gtc());}struct Segment_Tree{ ?Segment_Tree *ch[2]; ?int size;}node[N*150],*add[N],*red[N],*null,*root[N];int cnt1,cnt2;int n,cnt;int val[N];struct V{ ?int to,next;}c[N<<1];int head[N],t,sz;int ote[N],weight[N],deep[N],size[N];int Ti,top[N],dfn[N],id[N];inline void Init(){ ?null=newnode; ?null->ch[0]=null->ch[1]=null; ?null->size=0; ?for(int i=1;i<=n;++i)root[i]=null;}inline void U1(Segment_Tree *&p,int l,int r,int pos){ ?--p->size; ?if(l==r)return; ?if(pos<=mid)U1(p->ch[0],l,mid,pos); ?else U1(p->ch[1],mid+1,r,pos);}inline void U2(Segment_Tree *&p,int l,int r,int pos){ ?if(p==null)p=newnode,p->ch[0]=p->ch[1]=null,p->size=0; ?++p->size; ?if(l==r)return; ?if(pos<=mid)U2(p->ch[0],l,mid,pos); ?else U2(p->ch[1],mid+1,r,pos);}inline int Q(int l,int r,int k){ ?if(l==r)return l; ?register int sum=0,i; ?for(i=1;i<=cnt1;++i) ???sum+=add[i]->ch[1]->size; ?for(i=1;i<=cnt2;++i) ???sum-=red[i]->ch[1]->size; ?if(sum>=k){ ???for(i=1;i<=cnt1;++i) ?????add[i]=add[i]->ch[1]; ???for(i=1;i<=cnt2;++i) ?????red[i]=red[i]->ch[1]; ???return Q(mid+1,r,k); ?}else{ ???for(i=1;i<=cnt1;++i) ?????add[i]=add[i]->ch[0]; ???for(i=1;i<=cnt2;++i) ?????red[i]=red[i]->ch[0]; ???return Q(l,mid,k-sum); ?}}inline void Q1(int pos){ ?for(;pos>0;pos-=pos&(-pos)) ???add[++cnt1]=root[pos],cnt+=root[pos]->size;}inline void Q2(int pos){ ?for(;pos>0;pos-=pos&(-pos)) ???red[++cnt2]=root[pos],cnt-=root[pos]->size;}inline void U(int pos,int val0,int val){ ?for(;pos<=n;pos+=pos&(-pos)) ???U1(root[pos],0,Inf,val0),U2(root[pos],0,Inf,val);}inline void U(int pos,int val){ ?for(;pos<=n;pos+=pos&(-pos)) ???U2(root[pos],0,Inf,val);}inline void addedge(int x,int y){ ?c[++t].to=y,c[t].next=head[x],head[x]=t;}inline void dfs1(int x,int OPai){ ?ote[x]=OPai,deep[x]=deep[OPai]+1; ?size[x]=1; ?for(int i=head[x];i;i=c[i].next) ???if(c[i].to!=OPai){ ?????dfs1(c[i].to,x); ?????size[x]+=size[c[i].to]; ?????if(size[c[i].to]>size[weight[x]]) ???????weight[x]=c[i].to; ???}}inline void dfs2(int x,int tp){ ?dfn[x]=++Ti,id[Ti]=x,top[x]=tp; ?if(weight[x]==0)return; ?dfs2(weight[x],tp); ?for(int i=head[x];i;i=c[i].next) ???if(c[i].to!=ote[x]&&c[i].to!=weight[x]) ?????dfs2(c[i].to,c[i].to);}inline void Q(int x,int y){ ?while(top[x]!=top[y]){ ???if(deep[top[x]]<deep[top[y]])std::swap(x,y); ???Q1(dfn[x]),Q2(dfn[top[x]]-1); ???x=ote[top[x]]; ?} ?if(deep[x]<deep[y])std::swap(x,y); ?Q1(dfn[x]),Q2(dfn[y]-1);}int main(){ ?int T; ?read(n),read(T),Init(); ?for(int i=1;i<=n;++i)read(val[i]); ?for(int i=1,x,y;i<n;++i){ ???read(x),read(y); ???addedge(x,y),addedge(y,x); ?} ?dfs1(1,0),dfs2(1,1); ?for(int i=1;i<=n;++i) ???U(dfn[i],val[i]); ?int k,a,b; ?while(T--){ ???read(k),read(a),read(b); ???if(k==0){ ?????U(dfn[a],val[a],b),val[a]=b; ?????continue; ???} ???cnt1=cnt2=0; ???cnt=0,Q(a,b); ???if(cnt<k){ ?????puts("invalid request!"); ?????continue; ???} ???printf("%d\n",Q(0,Inf,k)); ?}return 0;}