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;