定义

树链剖分并不是一种算法或者数据结构,而是一种解决树上问题的思想。树链剖分的主要思想是把树上的路径以"轻重边路径剖分"的策略分成条链,并用数据结构维护这些链来解决树上的问题。

剖分

第一遍dfs,对于第个节点,记录的父亲节点,在树中的深度,以及以为根的子树大小,复杂度为

    void dfs1(int u)
    {
        size[u] = 1;
        for(int i = pre[u] ; i ; i = next[i] )
            if(to[i] != fa[u])
            {
                deep[to[i]] = deep[u] + 1;
                fa[to[i]] = u;
                dfs1(to[i]);
                size[u] += size[to[i]];
            }
    }

第二次dfs,对于第个节点,如果以这个节点为根的子树不是的最大子树,那么对于这个节点新建一条链,否则就加入所在的链。

同时在dfs时优先遍历,并记录每一个节点被访问的时间,以保证一条链上的点的序列是连续的。

    void dfs2(int u , int idx)
    {
        int max_child = 0;
        pos[u] = idx;
        dfn[u] = ++_dfs_clock;
        for(int i = pre[u] ; i ; i = next[i] )
            if(to[i] != fa[u] && size[to[i]] > size[max_child]) max_child = to[i];
        if(!max_child) return;
        dfs2(max_child , idx);
        for(int i = pre[u] ; i ; i = next[i] )
            if(to[i] != fa[u] && to[i] != max_child) dfs2(to[i] , to[i]);
    }

对之前那一棵树进行树链剖分然后我们就可以得到一个这样的森林

然后我们就可以根据dfn序列来用数据结构维护了

路径信息查询

对于树上的不同的两点,假设要求查询路径上的点权和。

如何利用树链剖分解决呢?不妨设

如果不在一条链上,那可以从深度较小的那个点开始跳到链首,累计这条链上的和
如果在一条链上,

只要重复这个过程,就能得到答案。同时,一般来说,两点间的信息维护都可以用这种思想来得以解决。

由于"轻重边路径剖分"策略的存在,经过树链剖分后链的数量是级别的,设数据结构维护信息的时间复杂度为那么树链剖分一次询问的复杂度是的。

Code

P2590 [ZJOI2008]树的统计
Problem 1036: [ZJOI2008]树的统计Count

通过一些奥妙重重的手段用朴素的树剖在luogu上拿了rank2
完整代码:

#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
#include <bits/stdc++.h>
using namespace std;

const  int  int_INF = 2147483647;

#define DEBUG(...) fprintf(stderr,__VA_ARGS__)
#define IL inline

struct IO_Tp
{
    static const int _Buf_Size = 1 << 26;

    char _Buf_I[_Buf_Size] , *_Buf_I_Pos;
    char _Buf_O[_Buf_Size] , *_Buf_O_Pos;

    int  _val;
    char _str[20] , *_pos;

    IO_Tp() : _Buf_I_Pos(_Buf_I) , _Buf_O_Pos(_Buf_O)  , _pos(_str) { fread(_Buf_I , 1 , _Buf_Size , stdin); }
    ~IO_Tp() { fwrite(_Buf_O , 1 , _Buf_O_Pos - _Buf_O , stdout); }

    template<class Type>
    IL IO_Tp& operator >> (Type &res)
    {
        res = 0 ;_val = 1;
        while(!isdigit(*_Buf_I_Pos)) _val = (*_Buf_I_Pos == '-' ? -1 : 1) , ++_Buf_I_Pos;
        do (res *= 10) += (*_Buf_I_Pos++) & 15; while(isdigit(*_Buf_I_Pos));
        res *= _val;
        return *this;
    }

    template<class Type>
    IL IO_Tp& operator << (Type val)
    {
        if(val < 0) *_Buf_O_Pos++ = '-' , val = -val;
        do *_pos++ = 48 + val % 10; while(val /= 10);
        while(_pos != _str) *_Buf_O_Pos++ = *--_pos;
        return *this;
    }

    IL IO_Tp& operator << (char ch)
    {
        *_Buf_O_Pos++ = ch;
        return *this;
    }

    IL IO_Tp& operator >> (char &ch)
    {
        while(!isupper(*_Buf_I_Pos)) _Buf_I_Pos++;
        ch = *_Buf_I_Pos++;
        return *this;
    }

} IO;

const int maxn = 30000 + 5;

namespace Tree
{
    int to[maxn << 1] , next[maxn << 1] , pre[maxn];
    int sz_edge = 1;

    void addedge(int u , int v)
    {
        to[sz_edge] = v;
        next[sz_edge] = pre[u];
        pre[u] = sz_edge++;
    }

    int deep[maxn] , fa[maxn] , size[maxn];

    void dfs1(int u)
    {
        size[u] = 1;
        for(int i = pre[u] ; i ; i = next[i] )
            if(to[i] != fa[u])
            {
                deep[to[i]] = deep[u] + 1;
                fa[to[i]] = u;
                dfs1(to[i]);
                size[u] += size[to[i]];
            }
    }

    int _dfs_clock , sz_chain = 1;
    int dfn[maxn] , pos[maxn];

    void dfs2(int u , int idx)
    {
        int max_child = 0;
        pos[u] = idx;
        dfn[u] = ++_dfs_clock;
        for(int i = pre[u] ; i ; i = next[i] )
            if(to[i] != fa[u] && size[to[i]] > size[max_child]) max_child = to[i];
        if(!max_child) return;
        dfs2(max_child , idx);
        for(int i = pre[u] ; i ; i = next[i] )
            if(to[i] != fa[u] && to[i] != max_child) dfs2(to[i] , to[i]);
    }

    int val[maxn];

    void split()
    {
        deep[1] = 1;
        dfs1(1);
        dfs2(1 , 1);
    }
}

namespace SegmentTree
{
    int Sum[maxn << 2] , Max[maxn << 2];

    #define lson rt<<1,l,mid
    #define rson rt<<1|1,mid+1,r

    void pushup(int rt)
    {
        Sum[rt] = Sum[rt << 1] + Sum[rt << 1 | 1];
        Max[rt] = max(Max[rt << 1] , Max[rt << 1 | 1]);
    }

    void build(int rt , int l , int r)
    {
        if(l == r)
        {
            Sum[rt] = Max[rt] = Tree::val[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(lson) , build(rson);
        pushup(rt);
    }

    void update(int rt , int l , int r , int k ,int x)
    {
        if(l == r)
        {
            Sum[rt] = Max[rt] = x;
            return;
        }
        int mid = (l + r) >> 1;
        if(k <= mid) update(lson , k , x);
        else update(rson , k , x);
        pushup(rt);
    }

    int queryMax(int rt , int l , int r , int a ,int b)
    {
        if(l >= a && r <= b) return Max[rt];
        int mid = (l + r) >> 1;
        int res = -int_INF;
        if(a <= mid) res = max(res , queryMax(lson , a , b));
        if(b > mid) res = max(res , queryMax(rson , a , b));
        return res;
    }

    int querySum(int rt , int l , int r , int a ,int b)
    {
        if(l >= a && r <= b) return Sum[rt];
        int mid = (l + r) >> 1;
        int res = 0;
        if(a <= mid) res += querySum(lson , a , b);
        if(b > mid) res += querySum(rson , a , b);
        return res;
    }
}

int n , m , x , y;
char opt;

using namespace Tree;
using namespace SegmentTree;

void printMax(int l , int r)
{
    int res = -int_INF;
    while(pos[l] != pos[r])
    {
        if(deep[pos[l]] < deep[pos[r]]) swap(l , r);
        res = max(res , queryMax(1 , 1 , n , dfn[pos[l]] , dfn[l]));
        l = fa[pos[l]];
    }
    if(dfn[l] > dfn[r]) swap(l , r);
    res = max(res , queryMax(1 , 1 , n , dfn[l] , dfn[r]));
    IO << res << '\n';
}

void printSum(int l , int r)
{
    int res = 0;
    while(pos[l] != pos[r])
    {
        if(deep[pos[l]] < deep[pos[r]]) swap(l , r);
        res += querySum(1 , 1 , n , dfn[pos[l]] , dfn[l]);
        l = fa[pos[l]];
    }
    if(dfn[l] > dfn[r]) swap(l , r);
    res += querySum(1 , 1 , n , dfn[l] , dfn[r]);
    IO << res << '\n';
}

int main()
{
    IO >> n;
    for(int i = 1 ; i < n ; i++ )
    {
        IO >> x >> y;
        addedge(x , y) , addedge(y , x);
    }
    split();
    for(int i = 1 ; i <= n ; i++ ) IO >> val[dfn[i]];
    build(1 , 1 , n);
    IO >> m;
    for(int i = 1 ; i <= m ; i++ )
    {
        IO >> opt;
        if(opt == 'Q')
        {
            IO >> opt >> x >> y;
            if(opt == 'S') printSum(x , y);
            else printMax(x , y);
        }
        else
        {
            IO >> x >> y;
            update(1 , 1 , n , dfn[x] , y);
        }
    }
    return 0;
}

Quote

树链剖分学习笔记
【bzoj1036】[ZJOI2008]树的统计Count

一些题解

一些关于树链剖分的题的题解,由于题目太水就不放代码了。

NOI2015软件包管理器

很水的一道树剖模板题吧,但是调了好久……
安装就是将根节点到的路径上点权全部置1,求sum的差值
卸载就是将以为根的子树全部删除,求sum的差值
线段树区间求和+区间赋值复杂度
代码

[SDOI2011]染色

区间赋值跟区间求和,维护颜色段数只要在合并的时候比较相连处的颜色是否相同,如果相同减一即可
代码

有好题再更吧现在一些题质量都太低了。

4 对 “树链剖分学习笔记”的想法;

发表评论

电子邮件地址不会被公开。 必填项已用*标注