树链剖分_树链剖分模板 - CSDN
精华内容
参与话题
  • 树链剖分树链剖分讲解

    千次阅读 2016-05-17 12:26:18
    如果不进行剖分代价会很大:对上边(u,v)中的边权查询修改,必然要将边权建立成搜索或查询进行维护,对于所有边建立后对于(u,v)修改时只能将(u,v)中所有边进行遍历修改,最坏代价(退化成)为n*查询...
    • 是什么?
      将树的所有边剖分成重边和轻边从而便于维护边权信息和进行修改,应对一系列大数据树上修改查询问题。
    • 为什么?
      如果不进行剖分代价会很大:对树上边(u,v)中的边权查询修改,必然要将边权建立成搜索树或查询树进行维护,对于所有边建立后对于(u,v)修改时只能将(u,v)中所有边进行遍历修改,最坏代价(退化成链)为n*查询修改代价。而如果把(u,v)中的边变成连续的一段区间,就会大大降低时间代价。
    • 怎么做?
      {正常的题解在这里都会下一堆定义,什么重边重孩子,我觉得不容易理解}
      想把(u,v)这条边变成一段可以查找的连续区间,一定要对边进行一个重新的分类和排序,对于检索也会有要求,如果我不能把(u,v)变成一段全连续的区间,但是如果能变成几部分也是很好的。
      而相对理想的就是变成log2n个区间。
      有的人说树链剖分就是把树边hash到log2n个区间上。
      下面我只能开始下定义了(由于本人才疏学浅,没法证明根到某一点中轻重边不大于log2n,也没法证明这个是怎么想到的)

    • 首先记:
      节点n子树节点数个数size[n];
      节点n深度deep[n];
      节点n父节点fa[n];

    • 重孩子:儿子节点所有孩子中size最大的;
    • 轻孩子:儿子节点中除了重儿子的;
    • 重边:连接重儿子的边;
    • 轻边:连接轻儿子的边;
    • 重链:重边连成的链;
    • 轻链:轻边连成的链;

    • 再定义:
      hson[n]表示n的重儿子标号;
      top[n]表示n在的重链的顶节点,不在重链上为自己标号。
      id[n]表示剖分后的节点标号;

    • 性质
      从根节点到任意节点路径上轻重边数量不大于log2n(别问我为什么);

    • 实现方法
      其实很简单,第一遍跑一遍dfs求出刚才说的size,deep,hson;
      然后再一遍dfs求出top,id;
      对应id算出val[id]表示id这个点下面连的边的权值。
      对val建检索树,排序树。

    • 重点
      查询的时候这么查:
      对(n,v)这条边:
      如果n,v在一条重边上,就直接查询(id[n],id[v])这一段区间即可。
      如果你,v不在一条重边上,就尽量向一条重边上靠,查询(id[n],id[top[n]]),n再跳到fa[top[n]]上,继续做,知道fa[top[n]]与v在一条重链上,就回到了上一种情况。
      这里也有一些细节,因为题中往往给的边都不是按深度给的,所以对于u,v,要注意深度关系,进行交换

    好了,这样我们就成功解决了对树上修改查询边权或点的问题。

    下面放上代码:

    vector<int> v[MAXN];
    int size[MAXN],dep[MAXN],val[MAXN],id[MAXN],hson[MAXN],top[MAXN],fa[MAXN];//定义
    int edge=1,num=1;
    struct tree{
        int x,y,z;
        void init(){scanf("%d%d%d",&x,&y,&z);}
    }e[MAXN];//起点重点权值
    void dfs1(int d,int f,int u){//d:深度 f:父节点 u:当前节点
        dep[u]=d;
        size[u]=1;
        hson[u]=0;
        fa[u]=f;
        for(vector<int>::iterator it=v[u].begin();it!=v[u].end();it++){
            if(*it==f) continue;
            dfs1(d+1,u,*it);
            size[u]+=size[*it];
            if(size[hson[u]]<size[*it])
                hson[u]=*it;//找重儿子
        }
    }
    void dfs2(int u,int tp){
        top[u]=tp;//赋值top
        id[u]=num++;//赋值id
        if(hson[u]) dfs2(hson[u],tp);//优先重儿子
        for(vector<int>::iterator it=v[u].begin();it!=v[u].end();it++){
            if(*it==fa[u]||*it==hson[u]) continue;
            dfs2(*it,*it);
        }
    }

    赋值val:节点与父亲的边

    for(int i=1;i<n;i++){  
        if(dep[e[i].x]<dep[e[i].y])
            swap(e[i].x, e[i].y);  
              val[id[e[i].x]] = e[i].z;  
    }  

    查询:只要不在一条重链上,(深度大的)就向父节点靠

    int find(int u,int v){
        int t1=top[u],t2=top[v];
        int ans=0;
        while(t1!=t2){
            if(dep[t1]<dep[t2]){
                swap(t1,t2);
                swap(u,v);
            }
            ans=max(query(1,id[t1],id[u]),ans);
            u=fa[t1];
            t1=top[u];
        }
        if(u==v) return ans;
        if (dep[u] > dep[v]) swap(u, v);  
            ans = max(query(1,id[hson[u]], id[v]), ans);  
            return ans;
    }

    val就用线段树平衡树维护一下就行了,这里就不附代码。

    展开全文
  • 树链剖分详解

    千次阅读 多人点赞 2018-05-11 19:44:29
    什么是树链剖分 树链剖分,它可以对一棵树进行轻重链剖分后用数据结构来维护每条重链。 比如下面这个问题:假设每个点有一个点权。如何把一棵树上的两个点uuu,vvv之间的简单路径上的所有点的点权增加ddd? 这就是...

    食用之前请务必搞清楚线段树

    什么是树链剖分

    • 树链剖分,它可以对一棵树进行轻重链剖分后用数据结构来维护每条重链。
    • 比如下面这个问题:假设每个点有一个点权。如何把一棵树上的两个点u,v之间的简单路径上的所有点的点权增加d
    • 这就是树链剖分能够解决的的一个基本问题。
    • 接下来介绍一下树链剖分的详细过程。

    轻重链剖分

    • 树链剖分的第一步就是将一棵树进行轻重链剖分。这一步决定了整个树链剖分的时间复杂度
    引入几个概念:
    • size[u]:以u为根的子树大小
    • wson[u]:在u的儿子中size值最大的那一个,称作u的重儿子
    • dfn[u]:每个点的dfs序号。pre[tot],如果dfn[u]=tot,则pre[tot]=u
    • 重链:指每个点与它的重儿子之间的连边(uwson[u])
    • 轻链:在所有边中不是重的其他边

    举个例子来详细说一下。
    树链剖分

    • 如上图(一张从百度百科挖来的图),每一个带红点的点就是轻儿子;每一条加粗的的边就是重链,没有加粗的就是轻边。比如说对于点2,那么
      wson[2]=6,size[2]=5,size[wson[u]]=size[6]=3
    • dfn[u]的含义就要稍微的特殊一些。因为它不仅仅是简单的dfs序号,而是按照轻重链的顺序来定义的。每次从一个点u往下dfs的时候,优先对wson[u]进行dfs,然后再遍历轻儿子们。
    • 比如说上图,每条边上有一个序号。把这个序号看做是点的(比如说1->4上面的1应该是dfn[4])。从1开始dfs,可以明显的看到是先对4进行dfs,然后再对wson[4]也就是9进行dfs….到了叶子节点再回溯去dfs轻儿子。
    • 为什么要这样做呢?因为这样之后,可以看到,每一条长重链上的每个点的dfn是连续的。比如1->4->9->13->14这条长重链上的dfn便是连续的,其他两条也一样。这样一来,就可以用维护区间的数据结构(比如线段树)来维护重链上的信息。
    树链剖分的好处
    • 一个上面已经说了,就是重链上的dfn是连续的,可以用数据结构维护
    • 还有就是,在每一条由根到叶子结点的路径上,轻链的条数和重链的长度均不会超过logn。这个性质决定了树链剖分的时间复杂度。如果是拿线段树来维护链的话,复杂度就是nlog2n
    代码实现轻重链剖分
    • 一共需要两个dfs。
    • 第一个用来处理每个点的基础信息(wson,size,dep,fa

    第一个dfs代码:

    inline dfs1(int u, int f)//两个参数:u是现在的点,f是u的父亲
    {
        size[u] = 1;//最开始u的子树中只有u一个点
        for(edge *p = head[u]; p; p = p->next)//遍历每一个与u相连的点
        {
            int v = p->v;
            if(v == f) continue;//如果此点是u的父亲就跳过
            dep[v] = dep[u] + 1;
            fa[v] = u;//处理信息
            dfs1(v, u);//继续递归
            size[u] += size[v];//u的子树大小要加上v的子树大小
            if(size[wson[u]] < size[v]) wson[u] = v;//更新重儿子
        }
    }
    • 这样就用一个dfs处理出了每个点的信息。
    • 再用第二个dfs求出每个点的dfn以及该点所处的链的链首。

    代码:

    inline void dfs2(int u, int tp)//u是当前点,tp是该链链首
    {
        dfn[u] = ++tot, pre[tot] = u, top[u] = tp;
        //pre是dfn的反函数。如dfn[2] = 3,pre[3] = 2...
        //为什么要有这个反函数,因为在建线段树的时候是用dfn建的,然而如果想要知道原来那个点的信息就要知道pre
        if(wson[u]) dfs2(wson[u], tp);//有重子就继续往下拉重链
        for(edge * p = head[u]; p; p = p->next)//回过头来在轻儿子中拉链
        {
            int v = p->v;
            if(v != fa[u] && v != wson[u]) dfs2(v, v);//如果不是爸爸或重儿子,已该点为链首继续拉链
        }
    }

    至此,轻重链剖分完成,然后便是第二大块——

    线段树维护重链

    • 就是用线段树维护重链上的信息。
    • 注意事项:这里所有的参数都是以dfn的形象出现的,而不是原来那个点的序号。
    inline void build(node *r, int left, int right)
    {
        r->left = left, r->right = right, r->lazy = -1, r->s = 0;
        if(left == right)
        {
             r->s = value[pre[left]];
             //这里是pre[left]不是left!原因就是刚才说的:这里所有的参数都是以dfn的形象出现的,而不是原来那个点的序号。
             return ;
        }
        int mid = (left + right) / 2;
        node *lson = &pool[++cnt], *rson = &pool[++cnt];
        r->ch[0] = lson, r->ch[1] = rson;
        build(lson, left, mid); build(rson, mid + 1, right);
        pushup(r);
    }

    基础的查询修改操作(在重链上的)就是原来的函数,怎么写详细请看线段树基础

    最后一步,也就是——

    两点间路径的修改&查询

    • 就是最开始提到的问题:如何把一棵树上的两个点u,v之间的简单路径上的所有点的点权增加d

    上图
    这里写图片描述

    Q1:如果想要求11与2之间的和该怎样?
    A1:在同一重链上,直接调用query查询就行了。

    • 在同一重链上的两点都可以直接查询

    Q2:求6与7之间的和?
    A2:将6跳到1,同时答案加上query(dfn[2],dfn[6]);然后将7跳到1,答案加上query(dfn[3],dfn[7])

    • 在不同重链上的两个点就一直按重链向上跳,直到跳到同一条重链上—>Q1

    代码(修改的):

    inline void modify(int u, int v, int d)
    {
        while(top[u] != top[v]) //直到跳到一条链上
        {
            if(dfn[top[u]] < dfn[top[v]]) swap(u, v);//这里根据链首的值交换一下
            change(root, dfn[top[u]], dfn[u], d), u = fa[top[u]];//最后u=链首的爸爸
        }
        if(dep[u] > dep[v]) swap(u, v);
        change(root, dfn[u], dfn[v], d);
        //Q1
    }

    查询的(基本类似):

    inline int Qsum(int u, int v)
    {
        int ret = 0;
        while(top[u] != top[v]) 
        {
            if(dfn[top[u]] < dfn[top[v]]) swap(u, v);
            ret += query(root, dfn[top[u]], dfn[u]), u = fa[top[u]];
        }
        if(dep[u] > dep[v]) swap(u, v);
        ret += query(root, dfn[u], dfn[v]);
        return ret;
    }

    至此基本完结

    类模板题

    CF343D,[NOI2015]软件包管理器,[SHOI2012]魔法树,[SDOI2011]染色,[ZJOI2008]树的统计

    展开全文
  • 所谓树剖——树链剖分,就是赋予一个链的概念来优化一些或者说是应对一些操作的,所以相应的会有一些专用的概念定义。 一个节点的重儿子,为其更大的一颗子树的根节点。从这个点连向重儿子的边我们称为重边。 ...

    初见安~~~终于学会了树剖~~~

    【兴奋】当初机房的大佬在学树剖的时候我反复强调过:“学树剖没有前途的!!!”

    恩。真香。

    一、重链与重儿子

    所谓树剖——树链剖分,就是赋予一个链的概念来优化一些或者说是应对一些操作的,所以相应的会有一些专用的概念定义。

     

    一个节点的重儿子,为其更大的一颗子树的根节点。从这个点连向重儿子的边我们称为重边。

    这里我们定义子树的大小是取决于节点的数量,而和点权没有任何关系。

    就比如在下图中:

    红色的边就是重边。

    我们一眼就可以发现——这些重边多多少少连成了一条链。而这些由重边连续连起来的点和边就组成了重链,也就是树链。

    我们可以发现树链的一些性质——比如,一条树链一定是一个轻儿子或者根节点开头,通过重边串起来一些重儿子;一个非叶子节点只有一个重儿子;一个单独的叶子节点也是一条树链,【满足以轻儿子开头】,所以一棵树一定可以被划分为几条链等等。

    那么树剖有什么用呢——处理树上的一些相关问题。比如——维护树上区间,树上路径等等。

    区间我们想到了线段树,树上路径想到了LCA,但是它们都有一个特点——连续。线段树只能维护连续区间,LCA路径也是不间断的。所以为了便于处理,我们要对这个图重新标号,以便查找。怎么标呢?我们可以想到——在树链上操作LCA路径,那么路径也是要连贯的,也就是说重链上的编号要连贯,所以我们重新编号的时候是在dfs序的基础上遵循先遍历重儿子的原则。

    二、例题

    我们还是以一个模板题为背景吧——洛谷P3384 【模板】树链剖分

    这个题有4个操作:

    操作1: 格式: 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z

    操作2: 格式: 2 x y 表示求树从x到y结点最短路径上所有节点的值之和

    操作3: 格式: 3 x z 表示将以x为根节点的子树内所有节点值都加上z

    操作4: 格式: 4 x 表示求以x为根节点的子树内所有节点值之和

    可以很容易发现——操作1、2都需要走一遍x到y的路径,操作3、4都需要操作以x为根的子树。所以我们先思考怎么遍历这些区间——

    首先遍历x到y的路径,我们亦容易想到LCA——两个点同时往上跳,直到某个值相同,可以一起操作。所以我们的思路就是:两个点不在同一条链就往链头的父亲节点跳,在同一条链上就直接处理。而处理方法也很简单——因为全程都在链上以连续的新节点编号来操作,所以线段树维护区间距离就很方便了,完全不受树剖影响地敲一个基本的建树、查询、区间修改+延迟标记的代码就可以了。【不清楚没关系,后面会有代码和详解】

    而对于操作3和4,以x为根的子树,显然编号也是连续的——毕竟编号时的最基本原则还是dfs遍历。但是有一个小问题——我们知道以x为根的子树最小的编号是x的编号,但是最大的编号我们并不知道,如果遍历一遍来找的话复杂度就会比较高了。所以——这是我们在初始化树剖的时候要存储下来的一个变量——以x为根的子树的最大的节点编号。也就是代码中的cnt[ ]。

    大致操作就如上啦~下面是代码及详解——

    #include<bits/stdc++.h>
    #define maxn 500010
    using namespace std;
    typedef long long ll;
    struct graph//关于存图的操作简单打个包
    {
    	struct edge
    	{
    		ll to, nxt;
    		edge(){}
    		edge(ll tt, ll nn)
    		{
    			to = tt;
    			nxt = nn;
    		}
    	}e[maxn << 1];
    	ll head[maxn], k = 0;
    	void init()
    	{
    		memset(head, -1, sizeof head);
    	}
    	
    	void add(ll u, ll v)
    	{
    		e[k] = edge(v, head[u]);
    		head[u] = k++;
    	}
    }g;
    
    struct node
    {
    	ll c, f;//c是区间和,f是延迟标记
    }t[maxn << 2];
    
    ll fa[maxn], dep[maxn], size[maxn], son[maxn];
    ll dfn[maxn], top[maxn], cnt[maxn], tot;
    //cnt——该子树最大节点编号(线段树上)dfn映射原标号与新标号
    ll n, m, root, val[maxn], mod;
    //val为节点上的值 
    //*****************************************************
    //关于初始化 
    //to find the heavy son
    void dfs_getson(ll u)//深优遍历初始化并得出重儿子
    {
    	size[u] = 1;
    	for(ll i = g.head[u]; ~i; i = g.e[i].nxt)
    	{
    		ll v = g.e[i].to;
    		if(v == fa[u]) continue;
    		fa[v] = u;
    		dep[v] = dep[u] + 1;
    		dfs_getson(v);
    		size[u] += size[v];
    		if(size[v] > size[son[u]]) son[u] = v;//这个儿子更大,这才是重儿子
    	}
    }
    
    void dfs_rewrite(ll u, ll tp)//找到链头
    {
    	top[u] = tp;
    	dfn[u] = ++tot; id[tot] = u;//映射到线段树上 
    	if(son[u]) dfs_rewrite(son[u], tp);//先遍历重链
    	for(ll i = g.head[u]; ~i; i = g.e[i].nxt)
    	{
    		ll v = g.e[i].to;
    		if(v != son[u] && v != fa[u]) dfs_rewrite(v, v);其他轻儿子的链
    	}
    	cnt[u] = tot; //回溯标记该子树最大编号
    }
    
    //*************************************************
    //关于线段树 【基本和线段树模板1一模一样
    void build(ll p, ll l, ll r)
    {
    	if(l == r) 
    	{
    		t[p].c = val[id[l]];//线段树上用的是新的编号
    		return; 
    	}
    	
    	ll mid = l + r >> 1;
    	build(p << 1, l, mid);
    	build(p << 1 | 1, mid + 1, r);
    	t[p].c = t[p << 1].c + t[p << 1 | 1].c;
    }
    
    void down(ll p, ll l, ll r)
    {
    	t[p << 1].f += t[p].f;
    	t[p << 1 | 1].f += t[p].f;
    	ll mid = l + r >> 1;
    	t[p << 1].c += t[p].f * (mid - l + 1);
    	t[p << 1 | 1].c += t[p].f * (r - mid);
    	t[p].f = 0;
    }
    
    void change(ll p, ll l, ll r, ll ls, ll rs, ll x)
    {
    	if(ls <= l && r <= rs)
    	{
    		t[p].c += (r - l + 1) * x;
    		t[p].f += x;
    		return;
    	}
    	if(t[p].f) down(p, l, r);
    	ll mid = l + r >> 1;
    	if(ls <= mid) change(p << 1, l, mid, ls, rs, x);
    	if(rs > mid) change(p << 1 | 1, mid + 1, r, ls, rs, x);
    	t[p].c = t[p << 1].c + t[p << 1 | 1].c;
    }
    
    ll getsum(ll p, ll l, ll r, ll ls, ll rs)
    {
    	if(ls <= l && r <= rs) 
    	{
    		
    		return t[p].c;
    	}
    	if(t[p].f) down(p, l, r);
    	ll mid = l + r >> 1;
    	ll ans = 0;
    	if(ls <= mid) ans += getsum(p << 1, l, mid, ls, rs), ans %= mod;
    	if(rs > mid) ans += getsum(p << 1 | 1, mid + 1, r, ls, rs), ans %= mod;
    	return ans;
    }
    //******************************************************
    //关于操作入口
    void change_xtoy()//1
    {
    	ll x, y, z;
    	scanf("%lld%lld%lld", &x, &y, &z);
    	while(top[x] != top[y])
    	{
    		if(dep[top[x]] > dep[top[y]]) swap(x, y);
    		change(1, 1, tot, dfn[top[y]], dfn[y], z);范围从y到y的链头
    		y = fa[top[y]];//深度更深的一个往上跳
    	}
    	if(dep[x] > dep[y]) swap(x, y);//on the same line
    	change(1, 1, tot, dfn[x], dfn[y], z);
    }
    
    void getson_xtoy()//2
    {
    	ll x, y;
    	scanf("%lld%lld", &x, &y);
    	ll ans = 0;
    	while(top[x] != top[y])
    	{
    		if(dep[top[x]] > dep[top[y]]) swap(x, y);
    		ans = (ans + getsum(1, 1, tot, dfn[top[y]], dfn[y])) % mod;		
    		y = fa[top[y]];
    	}
    	if(dep[x] > dep[y]) swap(x, y);
    	ans += getsum(1, 1, tot, dfn[x], dfn[y]);
    	prllf("%lld\n", ans % mod);
    }
    
    void change_sontree()//3
    {
    	ll x, y;
    	scanf("%lld%lld", &x, &y);
    	change(1, 1, tot, dfn[x], cnt[x], y);//直接操作
    }
    
    void getsum_sontree()//4
    {
    	ll x;
    	scanf("%lld", &x);
    	prllf("%lld\n", getsum(1, 1, tot, dfn[x], cnt[x]) % mod);
    } 
    
    ll main()
    {
    	g.init();
    	scanf("%lld%lld%lld%lld", &n, &m, &root, &mod);
    	for(ll i = 1; i <= n; i++) scanf("%lld", &val[i]);
    	for(ll i = 1; i < n; i++)
    	{
    		ll u, v;
    		scanf("%lld%lld", &u, &v);
    		g.add(u, v);
    		g.add(v, u);
    	}
    	
    	dfs_getson(root);
    	dfs_rewrite(root, root);//初始化
    	
    	build(1, 1, tot);
    	
    	for(ll i = 1; i <= m; i++)
    	{
    		ll op;
    		scanf("%lld", &op);
    		if(op == 1) change_xtoy();
    		if(op == 2) getson_xtoy();
    		if(op == 3) change_sontree();
    		if(op == 4) getsum_sontree();
    		
    	}
    	return 0;
    }

    也许这份代码看起来很长,(有很多丑陋的注释)但是核心的部分也就只有初始化的两个dfs函数和操作1、2的入口函数xtoy,加起来50行左右,所以树剖只要理解到了倒也挺简单的:)而在往后的各大知识点的学习中(什么LCT,DDP……反正我都不会)树剖更是作为了一个基础知识,所以一定要掌握好哇~~

    三、边转点

    最后,树剖+线段树可以维护的是树上的点权区间,如果是边权区间的话就要边转点。

    接下来特别讲一下关于树剖+线段树的边化点问题【清楚的自行跳过】

    边化点,顾名思义就是把边权转化为点权来用。而又因为每个点的父亲是唯一的,所以我们都是把边权给了深度更大的那个点。图上表示大概就是这样的:

    而后我们边化点,各个点的点权就是这样的:

    很明显,第一个点是没有值的。所以在边化点线段树维护操作完毕过后查询的时候要注意,搜索范围要么从2开始,要么赋值第一个点为极大值。还有就是,因为每个点所对应的边都是它到它父亲节点的边,所以最后我们查询区间或者修改区间的时候LCA那个点不能考虑进来,区间应为dfn[son[lca]]到dfn[]。

    可以看一个例题来强化一下:洛谷P1967 货车运输

    迎评:)
    ——End——

    展开全文
  • 何谓树链剖分? 就是将一棵树分成许多条链,使得树中所有节点都被包含在这些链里。 (换句话说:就是一种使你的代码瞬间增加1KB的算法。) 怎么剖分? 1.随便剖分 随便找一个节点,将它作为链头向下剖分。 2...

    知识准备

    1.DFS;
    2.线段树。
    相信DFS大家都会,估计只有线段树了。
    如果有不会的请点这里:线段树系列文章(未完)

    何谓树链剖分?

    就是将一棵树分成许多条链,使得树中所有节点都被包含在这些链里。

    (换句话说:就是一种使你的代码瞬间增加1KB的算法。)
    #怎么剖分?
    1.随便剖分

    随便找一个节点,将它作为链头向下剖分。

    2.随机剖分

    随便剖分+一点特判。

    3.轻重链剖分

    将重边(后面会讲)连成链。

    哪种方法好?

    显然,对于随机数据,三种方法没什么区别。

    但是对于第一、二种方法,若使用刻意构造的数据去测试,则会被卡掉。

    综上所述,为了保险起见,也为了算法稳定性,我们选择轻重链剖分。

    轻重链剖分

    Step1:乱七糟八的定义

    1. 重儿子:对于每个节点的儿子,若该儿子所在的子树的大小是所有儿子中最大的,则称该儿子为重儿子。每个节点有且只有一个重儿子。

    2. 轻儿子:除了重儿子的节点。

    3. 重边:连接重儿子与其父亲节点的边。

    4. 轻边:连接轻儿子与其父亲节点的边。

    5. 重链:由重边连接而成的链。注意链内有且只有重边。

    相信你也看不懂(hhh),举个例子吧:

    如图,在这棵树中:红框框着的点就是重儿子,紫色边表示重边,黑色边表示轻边。可以看出两条重链:{1,2,5,6}和{3,8,9}。而且,我们发现,重链的起点都是轻儿子。

    Step2:重标号?

    然后,我们可以对所有节点进行重编号(优先重儿子),就会得到如下的结果:(蓝色点即为新标号)

    我们发现:重链中,标号都是连续的。于是,我们可以想象一下:将所有重链按链首标号进行排序,并拉直平放起来;我们就得到了一个线性的序列。

    并且:我们可以发现一些性质:

    性质一:对于两个节点u,v,若v是u的轻儿子,则有:siz[v]<=siz[u]/2,若v是u的重儿子,则:siz[v]>siz[u]/2;

    性质二:对于一个任意节点u,它到根节点的路径最多有log2N\log_2 N条轻边,log2N\log_2N条重路径。

    Step3:数据结构:线段树

    接下来就很玄学了

    由上一步可知,我们得到了一个序列,于是,我们就可以把这一堆东西扔给线段树了。

    我们可以进行权值修改、路径查询等操作,而做到这一切,都只需要O(Nlog2N)O(N\log_2N)的时间复杂度。

    实现

    Step1:混乱的数组

    先扔来一堆数组名字:

    1. val[1...N]:记录每个节点的权值(读入时);
    2. siz[1...N]:记录以该节点为根的子树的大小;
    3. top[1...N]:记录每个节点所在重链的链首;
    4. son[1...N]:记录每个节点的重儿子;
    5. dep[1...N]:记录该节点在树中的深度;
    6. tid[1...N]:记录每个节点的新标号;
    7. rnk[1...N]:记录新标号所对应的节点,是tid的反函数;
    8. fa[1...N]:记录每个节点的父亲节点。

    晕了对吧?别慌,其实都非常有用的,理解了就非常容易。

    Step2:第一次DFS

    这次DFS我们主要处理一些基础信息,即:sizsondepfa四个数组。

    这种事情应该不会很困难吧?直接粘代码了。

    void DFS1(int u,int f,int d) {
        dep[u]=d,fa[u]=f,siz[u]=1;
        for(Tnode *p=G[u];p!=NULL;p=p->nxt) {
            int v=p->v;
            if(v==f)continue;
            val[v]=p->w;
            DFS1(v,u,d+1);
            siz[u]+=siz[v];
            if(son[u]==-1||siz[v]>siz[son[u]])
                son[u]=v;
        }
    }
    

    顺便粘上一份我使用的邻接表:

    struct Tnode {
    	int v,w;
    	Tnode *nxt;
    }e[2*Maxn+5];
    Tnode *G[Maxn+5],*ecnt=&e[0];
    void AddEdge(int u,int v,int w) {
        Tnode *p=++ecnt;
        p->v=v,p->w=w;
        p->nxt=G[u],G[u]=p;
         
        p=++ecnt;
        p->v=u,p->w=w;
        p->nxt=G[v],G[v]=p;
    }
    

    Step3:第二次DFS

    这次DFS主要处理剩下的信息:toptidrnk三个数组。

    我们在DFS传入一个参数tp,表示当前所在重链的链首,若遇到轻儿子则将tp设为该节点并继续往下传。

    在处理tidrnk时,我们开一个全局变量dcnt,每次进DFS时加一,就可以处理出这些信息了。代码如下:

    void DFS2(int u,int tp) {
        top[u]=tp,tid[u]=++dcnt,rnk[dcnt]=u;
        if(son[u]==-1)
            return;
        DFS2(son[u],tp);
        for(Tnode *p=G[u];p!=NULL;p=p->nxt) {
            int v=p->v;
            if(v==son[u]||v==fa[u])
                continue;
            DFS2(v,v);
        }
    }
    

    做完这些后,我们就完成了整个树链剖分的实现。

    剩下的就是各种数据结构的事情了。

    例题选讲

    例题1:SPOJ QTREE Query on a Tree

    展开全文
  • 树链剖分是解决树上问题的一种常见数据结构,对于树上路径修改及路径信息查询等问题有着较优的复杂度。树链剖分分为两种:重链剖分和长链剖分,因为长链剖分不常见,应用也不广泛,所以通常说的树链剖分指的是重链...
  • 洛谷 P3384 树链剖分(详解)

    千次阅读 2018-07-20 18:22:17
    如题,已知一棵包含N个结点的(连通且无环),每个节点上包含一个数值,需要支持以下操作: 操作1: 格式: 1 x y z 表示将从x到y结点最短路径上所有节点的值都加上z 操作2: 格式: 2 x y 表示求从x到...
  • 一、轻重边剖分的过程 使用两次dfs来实现。剖分过程中要计算如下7个值: father[x]:x在中的父亲 size[x]:x的子树结点数(子树大小) dep[x]:x在中的深度 son[x]:x的重儿子,即为重边 top[x]:x所在重路径的...
  • 辣鸡的我终于开始学树链剖分了,而ly聚聚早都会了QAQ..... 首先是一个板子题,就是板子 洛谷-P3384-【模板】树链剖分 题目链接:https://www.luogu.org/problemnew/show/P3384 题目大意:四种操作,板子。 思路...
  • 浅谈树链剖分

    千次阅读 2019-03-03 07:42:17
    什么是树链剖分? 指一种对树进行划分的算法,它先通过轻重边剖分将树分为多条链,保证每个点属于且只属于一条链,然后再通过数据结构(树状数组、SBT、SPLAY、线段树等)来维护每一条链,主要用来维护树上每条...
  • 一篇从浅到深探究一些上算法的博客
  • 树链剖分求LCA

    2018-06-12 17:01:15
    一、认识树链剖分 首先感谢https://www.cnblogs.com/George1994/p/7821357.html,看这篇文章让我对树链剖分有了很好的了解。下面自我梳理下。  它是为了将树型数据按照一定的规则线性化变成一条链,然后在树上的...
  • 树链剖分

    2019-05-13 07:25:26
    树链剖分(重链剖分)中的一些概念: 重儿子:所有儿子中子树节点数量最多的儿子。 轻儿子:除重儿子外的儿子。 重边:父亲和重儿子的边。 轻边:父亲和轻儿子的边。 重链:重边连成的链。 轻链:轻边连成的链。 为...
  • 树链剖分详解 模板

    2015-08-20 23:31:13
    原文地址:树链剖分作者:starszys  “在一棵树上进行路径的修改、求极值、求和”乍一看只要线段树就能轻松解决,实际上,仅凭线段树是不能搞定它的。我们需要用到一种貌似高级的复杂算法——树链剖分。  树...
  • 题目题目传送门题解树链剖分模版题,积累一下模版代码#include #include #include #include #include #define N 100005using namespace std;int n, m, Root, MOD, cur, head_p[N], Tim; in
  • 说到树链剖分,其实故事还挺多的。我记得在高中的OI经历中,我曾无数次听到这个名词,各种省赛、邀请赛貌似都会考这个东西,那时我觉得树链剖分深不可测,是我等蒟蒻不能理解的东西……然后我还记得,某年(好像是...
  • POJ 2763 树链剖分

    千次阅读 2016-07-11 14:15:00
    题意:给一个,然后上的边的边权,然后两个操作,一个是询问u到v的路上权值和,一个是将第几条边的权值修改 思路:与SPOJ 375 的那道题目很像,都是边上的权值,然后维护一个线段进行修改和求和就行了#...
  • codeforces 593D 树链剖分

    2015-11-12 19:02:10
    题目链接 给出一棵树,每棵树有value值,两种操作:1 u v x, 用x依次除以u到v... 直接树链剖分,然后用线段树维护乘积即可。注意 乘积可能爆long long , 可以用inf/a如果#include #include #include #define lson
  • 树链剖分-入门题目

    千次阅读 2016-11-12 16:38:02
    Query on a tree ... 题目大致意思就是: 给你一棵,有连个操作:  ● 第一个是查询任意两个不同节点上的最短路径上的最大权边!... ● 第二个操作修改某一条边的权值;...对于一棵,数的深度如果...所以我们就把分成一
  • 剖+线段裸题重的标号就是DFS序所以查子树的时候每回就 query(change[x],change[x]+size[x]-1) 就好了剩下的应该都会吧。。//By SiriusRen #include #include #include using namespace std; #define int ...
1 2 3 4 5 ... 20
收藏数 15,012
精华内容 6,004
关键字:

树链剖分