题解 CF916E 【Jamie and Tree】

zhengrunzhe · 2019-12-21 17:32:08 · 题解

update:satt找lca的non-local search做法本人已实现，讲解在下面

题意:

1.换根

2.找lca并将其子树加

3.子树求和

显然你可以去dfs序线段树什么的随便搞，但是太低级了

换根使人想到了lct，然后看到子树加使人放弃

这时候就需要用到一个动态树数据结构:toptree

并不是魔改lca(aaa树)，是真正的toptree

采用tarjan的self-adjusting实现

可以去negiizhao博客里学

动态找lca需要用non-local search

由于本人比较菜还不会实现non-local search

于是我就另外写了一个lct实现动态kca

具体如何实现有题去看就好了

做过sone1的都知道，satt去维护

簇路径和除簇路径以外部分的点权和

由于只有点权，所以可以省去base cluster

一个树的子树在satt上的表现就是access之后的中儿子(无需维护边顺序，compress node的四个儿子压成三个 两个rake儿子合成中儿子表示rake tree)

satt这个科技我并不想将代码公开，其实总共写了315行代码(跟我写的sone1一样长，如果会non-local search可以直接省掉lct的将近100行)

#include<cstdio>
#include<cstddef>
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 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);
namespace Self_Adjusting_Top_Trees
{
}
#define satt Self_Adjusting_Top_Trees
namespace Link_Cut_Trees
{
    struct tree
    {
        bool rev;
        tree *son[2],*fa;
        static tree *null;
        void *operator new(size_t size);
        void *operator new[](size_t size);
        inline tree():rev(0)
        {
            static bool init(0);
            if (!init)
                init=1,
                null=new tree,
                null->son[0]=null->son[1]=null->fa=null;
            son[0]=son[1]=fa=null;
        }
        inline const void reverse()
        {
            if (this!=null)swap(son[0],son[1]),rev^=1;
        }
        inline const void pushdown()
        {
            if (rev)
                son[0]->reverse(),
                son[1]->reverse(),
                rev=0;
        }
        inline const bool identity()
        {
            return fa->son[1]==this;
        }
        inline const bool isroot()
        {
            return fa->son[0]!=this&&fa->son[1]!=this;
        }
        inline const void rotate()
        {
            const bool f(identity());
            tree *fa(this->fa),*gfa(fa->fa),*q(son[f^1]);
            if (!fa->isroot())gfa->son[fa->identity()]=this;
            (son[f^1]=fa)->son[f]=q;
            ((q->fa=fa)->fa=this)->fa=gfa;
        }
        inline const void relieve()
        {
            if (!isroot())fa->relieve();
            pushdown();
        }
        inline const void splay()
        {
            for (relieve();!isroot();rotate())
                if (!fa->isroot())
                    (fa->identity()^identity()?this:fa)->rotate();
        }
    }*tree::null,*node0;
    #define null tree::null
    char memory_pool[N*sizeof(tree)],*tail(memory_pool+sizeof(memory_pool));
    inline void *tree::operator new(size_t size){return tail-=size;}
    inline void *tree::operator new[](size_t size){return tail-=size;}
    inline tree *node(const int &x){return node0+x;}
    inline tree *access(tree *x)
    {
        tree *y(null);
        for (;x!=null;x=(y=x)->fa)x->splay(),x->son[1]=y;
        return y;
    }
    inline const void evert(tree *x)
    {
        access(x);x->splay();x->reverse();
    }
    inline const void link(tree *x,tree *y)
    {
        evert(x);x->fa=y;
    }
    inline tree *lca(tree *x,tree *y)
    {
        access(x);return access(y);
    }
    #undef null
}
#define lct Link_Cut_Trees
int n,m;
int main()
{
    read(n);read(m);
    satt::node0=new satt::tree[n+1];
    lct::node0=new lct::tree[n+1];
    for (int i(1);i<=n;i++)read(satt::node(i)->val);
    for (int u,v,i(1);i<n;i++)
        read(u),read(v),
        satt::link(satt::node(u),satt::node(v)),
        lct::link(lct::node(u),lct::node(v));
    satt::evert(satt::node(1));lct::evert(lct::node(1));
    for (int opt,u,v,w;m--;)
        switch (read(opt),read(u),opt)
        {
            case 1:satt::evert(satt::node(u));lct::evert(lct::node(u));break;
            case 2:
            {
                read(v);read(w);
                const int lca(lct::lca(lct::node(u),lct::node(v))-lct::node0);
                satt::add(satt::node(lca),w);
                break;
            }
            case 3:printf("%lld\n",satt::query(satt::node(u)));break;
        }
    return 0;
}

non-local searching for lca:

记rt为根 lca为Lca(u,v)，dis(x,y)表示x,y路径上点数，则有

移项得

显然分子可以直接求出

这样我们就知道了lca到根的距离记作k，那我们只需要从根往下到u或v跳k个点即可

这个东西我们可以通过提取根到u或v的路径，因为root path形态是个Splay，然后在上面找kth即可

non-local search的本质是二分，类似线段树上二分

而toptree的簇结构构成就类似线段树，所以原理不难理解

平衡树kth的本质也是通过左儿子大小这一信息实现对二分的check

代码仍然不提供satt

#include<cstdio>
#include<cstddef>
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 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);
namespace Self_Adjusting_Top_Trees
{
}using namespace Self_Adjusting_Top_Trees;
int n,m;
int main()
{
    read(n);read(m);
    node0=new tree[n+1];
    for (int i(1);i<=n;i++)read(node(i)->val);
    for (int u,v,i(1);i<n;i++)
        read(u),read(v),link(node(u),node(v)),
    evert(root=node(1));
    for (int opt,u,v,w;m--;)
        switch (read(opt),read(u),opt)
        {
            case 1:evert(root=node(u));break;
            case 2:read(v);read(w);add(lca(node(u),node(v)),w);break;
            case 3:printf("%lld\n",query(node(u)));break;
        }
    return 0;
}