很裸的LCT维护子树信息。
很显然,如果选中的点从u到v,那么总代价是+P-Q,说白了只跟两侧的点数有关。
因此,只要从根出发,找每个儿子:如果满足其子数权值和*2超过了总权值和,那么向这条边走,一定会使得答案更优。
所以我们唯一需要做的,就是统计每个点的子树权值和即可。
只不过这题好在一不换根二不改子树,所以就那个set存一下虚儿子的信息即可。
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<set> #define SF scanf #define PF printf #define MAXN 1000010 using namespace std; int SumSiz; int fax[MAXN],val[MAXN]; struct node *NIL; struct node{ int siz,tag; node *ch[2]; node *fa,*ls; set<pair<int,node *> >S; bool Dir(){ return fa->ch[1]==this; } bool Isroot(){ return fa==NIL||(fa->ch[0]!=this&&fa->ch[1]!=this); } void Setchild(node *x,int d){ ch[d]=x; if(x!=NIL) x->fa=this; } void pushdown(){ if(tag){ if(ch[0]!=NIL) ch[0]->siz+=tag,ch[0]->tag+=tag; if(ch[1]!=NIL) ch[1]->siz+=tag,ch[1]->tag+=tag; tag=0; } } }Tree[MAXN]; node *ncnt=Tree,*rt; void Newnode(node *x,int k){ x->siz=k; x->ch[0]=x->ch[1]=x->fa=x->ls=NIL; } void Rotate(node *x){ int d=x->Dir(); node *y=x->fa; y->pushdown(),x->pushdown(); if(y->Isroot()) x->fa=y->fa; else y->fa->Setchild(x,y->Dir()); y->Setchild(x->ch[!d],d); x->Setchild(y,!d); } void Splay(node *x){ x->pushdown(); while(!x->Isroot()){ node *y=x->fa; if(y->Isroot()) Rotate(x); else{ if(x->Dir()==y->Dir()) Rotate(y); else Rotate(x); Rotate(x); } } } node *find_lft(node *x){ while(x->ch[0]!=NIL) x=x->ch[0]; return x; } void Access(node *x){ node *c=NIL; while(x!=NIL){ if(x->ls!=NIL) Splay(x->ls),x->S.insert(make_pair(x->ls->siz,x->ls)); Splay(x); x->Setchild(c,1); x->ls=find_lft(c); if(x->ls!=NIL) Splay(x->ls),x->S.erase(make_pair(x->ls->siz,x->ls)),Splay(x); c=x; x=x->fa; } } void link(node *x,node *y){ Access(x); Splay(y); x->fa=y; y->S.insert(make_pair(x->siz,x)); } void dfs(node *x){ x->pushdown(); if(x->ch[0]!=NIL) dfs(x->ch[0]); // PF("{%d %d}",x-Tree,x->siz); for(set<pair<int,node*> >::iterator it=x->S.begin();it!=x->S.end();it++) dfs(it->second); if(x->ch[1]!=NIL) dfs(x->ch[1]); } void change(node *x,int k){ Access(x); Splay(x); x->siz+=k; x->tag+=k; } node *find_ans(node *x){ if(x==NIL) return NIL; x->pushdown(); if(x->siz*2<SumSiz) return find_ans(x->ch[0]); if(x->S.size()){ pair<int,node*> las=*x->S.rbegin(); if(las.first*2>=SumSiz) return find_ans(las.second); } node *res=find_ans(x->ch[1]); if(res==NIL) return x; return res; } int Query(){ Splay(rt); node *x=find_ans(rt); Access(x); Splay(x); if(x->siz*2==SumSiz) return fax[x-Tree]; return x-Tree; } int main(){ freopen("jueban.in","r",stdin); freopen("jueban.out","w",stdout); NIL=Tree; NIL->ch[0]=NIL->ch[1]=NIL->fa=NIL->ls=NIL; int n,t,tag,u,lastans=0; SF("%d%d",&n,&t); SumSiz+=t; Newnode(++ncnt,t); val[1]=t; rt=ncnt; for(int i=1;i<=n;i++){ SF("%d",&tag); if(tag==1){ SF("%d%d",&u,&t); u^=lastans,t^=lastans; Newnode(++ncnt,0); SumSiz+=t; link(ncnt,u+Tree); change(ncnt,t); val[ncnt-Tree]=t; fax[ncnt-Tree]=u; } else if(tag==2){ SF("%d%d",&u,&t); u^=lastans,t^=lastans; change(u+Tree,t-val[u]); SumSiz+=(t-val[u]); val[u]=t; } else{ lastans=Query(); PF("%d\n",lastans); } // Splay(rt); // dfs(rt); // PF("\n"); } }