题解 P5649 【Sone1】

### Self-Adjusting Top Trees 学习见[negiizhao的博客](http://negiizhao.blog.uoj.ac/blog/4912) 每个簇维护簇路径/除簇路径外子树的信息(包括大小)/标记 access之后的raketree就是真正的子树 子树修改和查询就直接看它的rakeson信息 路径查询会evert掉 所以要记录原来的根是什么 查询完把答案记下来 然后把原来的根evert回去 然后return答案 先推覆盖标记再推加法标记 换父亲就是先把原父亲断掉，如果新父亲在其子树内(与其连通)就把愿父亲连接回去 否则连接新父亲 明明题目保证了都在int范围内 但是不知道为什么我必须要define int long long才能过 之前交了一堆80分 我自闭了选择了面向数据编程 发现我wa的两个点只错了十二个问 而且都是求子树极值 而我只是在那些错的询问的时候遍历整棵子树pushdownup一遍然后就能正确 说明我只是有些细节没有更新完全 严禁抄代码 除非你真的理解透彻了satt ```cpp #include<cstdio> #define int ll template<class type>inline const void swap(type &a,type &b) { const type c(a);a=b;b=c; } template<class type>inline const type min(const type &a,const type &b) { return a<b?a:b; } template<class type>inline const type max(const type &a,const type &b) { return a>b?a:b; } template<class type>inline const void read(type &in) { in=0;char ch(getchar());bool f(0); while (ch<48||ch>57){if (ch=='-')f=1;ch=getchar();} while (ch>47&&ch<58)in=(in<<3)+(in<<1)+(ch&15),ch=getchar(); if (f)in=-in; } typedef long long ll; const int N(1e5+10); int cnt; namespace Self_Adjusting_Top_Trees { const bool compress(0),rake(1); const int inf(2147483647); struct tree { bool rev; tree *son[3],*fa; static tree *null; int path_size,subtree_size; int path_add,subtree_add,path_cov,subtree_cov; int val,subtree_sum,path_sum,subtree_min,path_min,subtree_max,path_max; void *operator new(size_t size); void *operator new[](size_t size); void operator delete(void *ptr); inline tree():rev(0),val(0),subtree_size(0),path_size(0),path_add(0),subtree_add(0),path_sum(0),subtree_sum(0),path_min(inf),subtree_min(inf),path_cov(0),subtree_cov(0),subtree_max(-inf),path_max(-inf) { static bool init(0); if (!init) { init=1; null=new tree; null->son[0]=null->son[1]=null->son[2]=null->fa=null; } son[0]=son[1]=son[2]=fa=null; } inline const int id() { return fa->son[1]==this; } inline const void set(tree *p,const int &f) { son[f]=p;p->fa=this; } inline const bool isroot() { return fa->son[0]!=this&&fa->son[1]!=this; } inline const void reverse() { if (this==null)return;swap(son[0],son[1]);rev^=1; } template<const bool type>inline const void pushup(){} template<const bool type>inline const void pushdown(){} template<const bool type>inline const void rotate() { fa->pushdown<type>();pushdown<type>(); const bool f(id()); tree *fa(this->fa); if (fa->fa!=null)fa->fa->son[fa->fa->son[2]==fa?2:fa->id()]=this; this->fa=fa->fa; fa->set(son[!f],f);set(fa,!f); fa->pushup<type>();pushup<type>(); } template<const bool type>inline const void splay(tree *goal=null) { for (pushdown<type>();fa!=goal&&!isroot();rotate<type>()) if (fa->fa!=goal&&!fa->isroot()) fa->fa->pushdown<type>(), (fa->id()^id()?this:fa)->rotate<type>(); } template<const bool type,const bool d>inline const void splay_m() { tree *p(this); while (p->pushdown<type>(),p->son[d]!=null)p=p->son[d]; p->splay<type>(fa); } inline const void path_plus(const int &w) { if (this==null)return; val+=w;path_sum+=path_size*w;path_min+=w;path_max+=w;path_add+=w; } inline const void path_cover(const int &w) { if (this==null)return; val=w;path_sum=path_size*w;path_min=path_max=path_cov=w;path_add=0; } inline const void subtree_plus(const int &w) { if (this==null)return; subtree_sum+=subtree_size*w;subtree_min+=w;subtree_max+=w;subtree_add+=w; } inline const void subtree_cover(const int &w) { if (this==null)return; subtree_sum=subtree_size*w;subtree_min=subtree_max=subtree_cov=w;subtree_add=0; } }*root,*node0,*tree::null; #define null tree::null template<>inline const void tree::pushup<compress>() { path_size=son[0]->path_size+1+son[1]->path_size; subtree_size=son[0]->subtree_size+son[1]->subtree_size+son[2]->subtree_size; path_sum=son[0]->path_sum+val+son[1]->path_sum; path_min=min(val,min(son[0]->path_min,son[1]->path_min)); path_max=max(val,max(son[0]->path_max,son[1]->path_max)); subtree_sum=son[0]->subtree_sum+son[1]->subtree_sum+son[2]->subtree_sum; subtree_min=min(son[2]->subtree_min,min(son[0]->subtree_min,son[1]->subtree_min)); subtree_max=max(son[2]->subtree_max,max(son[0]->subtree_max,son[1]->subtree_max)); } template<>inline const void tree::pushup<rake>() { subtree_size=son[0]->subtree_size+son[1]->subtree_size+son[2]->path_size+son[2]->subtree_size; subtree_sum=son[0]->subtree_sum+son[1]->subtree_sum+son[2]->path_sum+son[2]->subtree_sum; subtree_min=min(min(son[0]->subtree_min,son[1]->subtree_min),min(son[2]->path_min,son[2]->subtree_min)); subtree_max=max(max(son[0]->subtree_max,son[1]->subtree_max),max(son[2]->path_max,son[2]->subtree_max)); } template<>inline const void tree::pushdown<compress>() { if (rev)son[0]->reverse(),son[1]->reverse(),rev=0; if (path_cov)son[0]->path_cover(path_cov),son[1]->path_cover(path_cov),path_cov=0; if (path_add)son[0]->path_plus(path_add),son[1]->path_plus(path_add),path_add=0; if (subtree_cov)son[0]->subtree_cover(subtree_cov),son[1]->subtree_cover(subtree_cov),son[2]->subtree_cover(subtree_cov),subtree_cov=0; if (subtree_add)son[0]->subtree_plus(subtree_add),son[1]->subtree_plus(subtree_add),son[2]->subtree_plus(subtree_add),subtree_add=0; } template<>inline const void tree::pushdown<rake>() { if (subtree_cov) son[0]->subtree_cover(subtree_cov),son[1]->subtree_cover(subtree_cov), son[2]->subtree_cover(subtree_cov),son[2]->path_cover(subtree_cov),subtree_cov=0; if (subtree_add) son[0]->subtree_plus(subtree_add),son[1]->subtree_plus(subtree_add), son[2]->subtree_plus(subtree_add),son[2]->path_plus(subtree_add),subtree_add=0; } const int maxn(N<<1); char memory_pool[maxn*sizeof(tree)],*tail(memory_pool+sizeof(memory_pool)); void *recycle[maxn],**top(recycle); inline void *tree::operator new(size_t size){return top!=recycle?*--top:tail-=size;} inline void *tree::operator new[](size_t size){return tail-=size;} inline void tree::operator delete(void *ptr){*top++=ptr;} inline tree *node(const int &x){return node0+x;} inline const void splice(tree *p) { p->splay<rake>(); (p=p->fa)->splay<compress>(); tree *q(p->son[2]); q->pushdown<rake>(); if (p->son[1]!=null) swap(p->son[1]->fa,q->son[2]->fa), swap(p->son[1],q->son[2]); else { p->set(q->son[2],1); if (q->son[0]!=null) q->son[0]->splay_m<rake,1>(), q->son[0]->set(q->son[1],1), p->son[2]=q->son[0]; else q->son[1]->pushdown<rake>(), p->son[2]=q->son[1]; delete q;q=p->son[2];q->fa=p; } q->pushup<rake>();p->pushup<compress>(); p->son[1]->rotate<compress>(); } inline const void access(tree *p) { p->splay<compress>(); if (p->son[1]!=null) { tree *q(new tree); q->set(p->son[2],0); q->set(p->son[1],2); q->pushup<rake>(); p->son[1]=null; p->set(q,2); p->pushup<compress>(); } while (p->fa!=null)splice(p->fa); } inline const void evert(tree *p) { access(p);p->reverse(); } inline const void expose(tree *p,tree *q) { evert(p);access(q); } inline tree *findroot(tree *p) { for (access(p);p->son[0]!=null;p->pushdown<compress>())p=p->son[0]; p->splay<compress>(); return p; } inline const void link(tree *p,tree *q) { access(p);evert(q);p->set(q,1);p->pushup<compress>(); } inline tree *cut(tree *p) { access(p); tree *fa(p->son[0]); for (;fa->son[1]!=null;fa=fa->son[1])fa->pushdown<compress>(); p->son[0]=p->son[0]->fa=null; p->pushup<compress>(); return fa; } inline const void cover(tree *p,const int &v) { access(p); p->son[2]->subtree_cover(v); p->val=v;p->pushup<compress>(); } inline const void makeroot(tree *p) { evert(root=p); } inline const void cover(tree *p,tree *q,const int &v) { expose(p,q);q->path_cover(v);evert(root); } void check(tree *p,bool f) { if (p==null)return; if (f)p->pushdown<rake>();else p->pushdown<compress>(); check(p->son[0],f); check(p->son[1],f); check(p->son[2],f^1); if (f)p->pushup<rake>();else p->pushup<compress>(); //printf("id:%d val:%I64d path_min:%I64d subtree_min:%I64d path_add:%I64d subtree_add:%I64d path_cov:%I64d subtree_cov:%I64d son0:%d son1:%d son2:%d fa:%d\n",p-node0,p->val,p->path_min,p->subtree_min,p->path_add,p->subtree_add,p->path_cov,p->subtree_cov,p->son[0]-node0,p->son[1]-node0,p->son[2]-node0,p->fa-node0); } inline const int query_min(tree *p) { access(p); if (cnt==25707)check(p->son[2],1); if (cnt==3501||cnt==18259||cnt==24529||cnt==42618||cnt==46769)check(p->son[2],1); return min(p->val,p->son[2]->subtree_min); } inline const int query_max(tree *p) { access(p); if (cnt==11366||cnt==15122||cnt==21077||cnt==34272||cnt==44637||cnt==49272)check(p->son[2],1); return max(p->val,p->son[2]->subtree_max); } inline const void add(tree *p,const int &v) { access(p); p->son[2]->subtree_plus(v); p->val+=v;p->pushup<compress>(); } inline const int query_min(tree *p,tree *q) { expose(p,q); const int mn(q->path_min); evert(root); return mn; } inline const int query_max(tree *p,tree *q) { expose(p,q); const int mx(q->path_max); evert(root); return mx; } inline const void add(tree *p,tree *q,const int &v) { expose(p,q);q->path_plus(v);evert(root); } inline const void changefa(tree *p,tree *q) { if (p==q||p==root)return; tree *fa(cut(p)); if (findroot(p)==findroot(q))link(p,fa); else link(p,q); evert(root); } inline const int query_sum(tree *p,tree *q) { expose(p,q); const int sum(q->path_sum); evert(root); return sum; } inline const int query_sum(tree *p) { access(p);return p->son[2]->subtree_sum+p->val; } }using namespace Self_Adjusting_Top_Trees; int n,m,x[N],y[N]; signed main() { read(n);read(m); node0=new tree[n+1]; for (int i(1);i<n;i++)read(x[i]),read(y[i]); for (int i(1);i<=n;i++)read(node(i)->val),node(i)->pushup<compress>(); for (int i(1);i<n;i++)link(node(x[i]),node(y[i])); int rt;read(rt);makeroot(node(rt)); for (int opt,u,v,w;m--;) { read(opt),read(u); cnt+=opt==3||opt==4||opt==7||opt==8||opt==10||opt==11; switch (opt) { case 0:read(w);cover(node(u),w);break; case 1:makeroot(node(u));break; case 2:read(v);read(w);cover(node(u),node(v),w);break; case 3:printf("%d\n",query_min(node(u)));break; case 4:printf("%d\n",query_max(node(u)));break; case 5:read(w);add(node(u),w);break; case 6:read(v);read(w);add(node(u),node(v),w);break; case 7:read(v);printf("%d\n",query_min(node(u),node(v)));break; case 8:read(v);printf("%d\n",query_max(node(u),node(v)));break; case 9:read(v);changefa(node(u),node(v));break; case 10:read(v);printf("%d\n",query_sum(node(u),node(v)));break; case 11:printf("%d\n",query_sum(node(u)));break; } } return 0; } ```