题解 P5649 【Sone1】

Self-Adjusting Top Trees

学习见negiizhao的博客

每个簇维护簇路径/除簇路径外子树的信息(包括大小)/标记

access之后的raketree就是真正的子树 子树修改和查询就直接看它的rakeson信息

路径查询会evert掉 所以要记录原来的根是什么 查询完把答案记下来 然后把原来的根evert回去 然后return答案

先推覆盖标记再推加法标记

换父亲就是先把原父亲断掉，如果新父亲在其子树内(与其连通)就把愿父亲连接回去 否则连接新父亲

明明题目保证了都在int范围内 但是不知道为什么我必须要define int long long才能过

之前交了一堆80分 我自闭了选择了面向数据编程

发现我wa的两个点只错了十二个问 而且都是求子树极值

而我只是在那些错的询问的时候遍历整棵子树pushdownup一遍然后就能正确

说明我只是有些细节没有更新完全

严禁抄代码 除非你真的理解透彻了satt

#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;
}