题解 P5649 【Sone1】
zhengrunzhe · · 题解
Self-Adjusting Top Trees
学习见negiizhao的博客
每个簇维护簇路径 (
如何调取节点
路径查询会调用
注意先推覆盖标记再推加法标记
换父亲就是先把原父亲断掉，如果新父亲在其子树内(即与其连通)就把原父亲连接回去，否则连接新父亲。
之前交了一堆80分，我自闭了发现我wa的两个点只错了十二个问，而且都是求子树极值。而我只是在那些错的询问的时候遍历整棵子树pushdownup一遍然后就能正确，说明有些细节没有更新完全。
感谢帖子 https://www.luogu.com.cn/discuss/347184 指出若整个子树没有虚子树的情况下(
代码仅供参考，请真的理解透彻了
#include<cstdio>
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;
}
const int N(1e5+10);
namespace SelfAdjustingTopTrees
{
const bool Compress(0),Rake(1);
const int inf(2147483647);
struct Tree
{
bool rev,path_flag,subtree_flag;
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_cov(0),subtree_cov(0),
path_sum(0),subtree_sum(0),
path_flag(0),subtree_flag(0),
path_min(inf),subtree_min(inf),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;
path_flag=1;
}
inline const void subtree_plus(const int &w)
{
if (this==Null)return;
if (!subtree_size)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;
if (!subtree_size)return;
subtree_sum=subtree_size*w;
subtree_min=subtree_max=subtree_cov=w;
subtree_flag=1;
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_flag)son[0]->path_cover(path_cov),son[1]->path_cover(path_cov),path_flag=0;
if (path_add)son[0]->path_plus(path_add),son[1]->path_plus(path_add),path_add=0;
if (subtree_flag)son[0]->subtree_cover(subtree_cov),son[1]->subtree_cover(subtree_cov),son[2]->subtree_cover(subtree_cov),subtree_flag=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_flag)
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_flag=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);
}
inline const int query_min(Tree *p)
{
access(p);
return min(p->val,p->son[2]->subtree_min);
}
inline const int query_max(Tree *p)
{
access(p);
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 SelfAdjustingTopTrees;
int n,m,x[N],y[N];
int 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);
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;
}