树链剖分

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
转移自老blog

树链剖分

       如果给出一棵树并为每个节点标号1234...n;并定义区间[x,y]为树上节点x到节点y的最短路所经过的所有节点组成的集合,注意是闭区间,包括x,y两个节点      

       树链剖分能够解决树上区间的操作,是线段树功能的强化版,但他也依赖着线段树。

       树链剖分尝试着把树分割为多条链,并按照dfs序对链排序并交给线段树维护,如果这个想法成立,那么所有的树上区间操作都成了多段区间的线段树操作。

       现在的问题转移到如何分链,能够保证任何树上区间进行分解时分出的链都较少?否则上诉尝试没有任何意义,前人给出了分法。按轻重链分,

       这里有必要介绍几种名词

               重儿子:父亲节点的所有儿子中子树结点数目最多(size最大)的结点;

               轻儿子:父亲节点中除了重儿子以外的儿子;

               重边:父亲结点和重儿子连成的边;

               轻边:父亲节点和轻儿子连成的边;

               重链:由多条重边连接而成的路径;

               轻链:由多条轻边连接而成的路径;

       如此想必读者已经知道如何去分了,但为什么这样分保证任何树上区间进行分解时分出的链都较少

简单证明:

       假设根编号为root

       则区间[x,y]分出的链一定少于[root,x][root,y]这两个区间分出的链的和

       问题可以简化为对于区间[root,x]分出的链的数量的复杂度的证明,

       我们尝试从根往节点x走,一走就走一整条剖分链,如果没有到达x,一定会走上一个轻儿子,每当走上一个轻儿子,问题递归为以轻儿子为根走向节点x,

       可以证明这样的走法每走一步,当前子树的节点数目减半,这是轻儿子的性质。

       我们顶多走Olgn步,这意味着分出的链为Olgn个。子问题证毕。

over

如何分链呢?

       两次dfs

       第一次记录父亲,记录子孙数量,回溯重儿子,

       第二次根据重儿子优先dfs,标记每个节点所属重链的起点,标记dfs序,

       依据dfs序把树变成链并交给线段树处理

       查询的时候便只需要依据每个节点所属重链起点和dfs序进行线段树区间查询,修改也是一样,都交给线段树处理



struct dissection:segment_tree,graph
{
    static const ll maxn=2.1e5;
    ll treen;
    ll dep[maxn],dad[maxn],son[maxn],siz[maxn],tid[maxn],chain[maxn];
    
    //siz,dep,son,dad,
    void dfs1(ll u=1,ll father=1,ll deep=1)
    {
        dep[u]=deep;
        dad[u]=father;
        siz[u]=1;
        for(ll i=head[u]; ~i; i=g[i].nex)
        {
            ll v=g[i].v;
            if(v!=father)
            {
                dfs1(v,u,deep+1);
                siz[u]+=siz[v];
                if (son[u]==-1||siz[v]>siz[son[u]])son[u]=v;
            }
        }
    }
    
    //chain,tid,rnk;
    void dfs2(ll u=1,ll s=1)
    {
        chain[u]=s;
        tid[u]=++treen;
        rnk[treen]=u;
        
        if(son[u]==-1)return;
        dfs2(son[u],s);
        for (ll i=head[u]; ~i; i=g[i].nex)
        {
            ll v=g[i].v;
            if(v!=son[u]&&v!=dad[u])dfs2(v,v);
        }
    }
    
    ll query_path(ll x,ll y)
    {
        ll ans=0;
        while(chain[x]!=chain[y])
        {
            if(dep[chain[x]]<dep[chain[y]])swap(x,y);
            ans+=query(tid[chain[x]],tid[x]);
            x=dad[chain[x]];
        }
        if(tid[x]>tid[y])swap(x,y);
        return ans+query(tid[x],tid[y]);
    }
    
    ll query_path_max(ll x,ll y)
    {
        ll ans=-1e9;
        while(chain[x]!=chain[y])
        {
            if(dep[chain[x]]<dep[chain[y]])swap(x,y);
            ans=max(ans,query_max(tid[chain[x]],tid[x]));
            x=dad[chain[x]];
        }
        if(tid[x]>tid[y])swap(x,y);
        return max(ans,query_max(tid[x],tid[y]));
    }
    
    void update_path(ll x,ll y,ll d)
    {
        while(chain[x]!=chain[y])
        {
            if(dep[chain[x]]<dep[chain[y]])swap(x,y);
            update(tid[chain[x]],tid[x],d);
            x=dad[chain[x]];
        }
        if(tid[x]>tid[y])swap(x,y);
        update(tid[x],tid[y],d);
    }
    
    void ini()
    {
        graph::ini();
    }
    
    void build()
    {
        treen=0;
        memset(son,-1,sizeof(son));
        dfs1();
        dfs2();
        segment_tree::build(treen);
    }
    
} tree;