树链剖分

阅读量：5754 次

发布时间：2019-06-18

本文共 8557 字，大约阅读时间需要 28 分钟。

什么是树链剖分

树链剖分并不是一个复杂的算法或者数据结构，它能把一棵树拆成链。

树链，就是树上的路径。剖分，就是把路径分类为重链和轻链。

给定一棵树，将它划分成若干条互不相交的路径，满足：从节点 u->v 最多经过 logn 条路径以及 logn 条不在路径上的边。

树链剖分后，我们就可以利用其它的数据结构对在一棵树上进行路径的修改、求极值、求和的一类问题进行求解了。

一些定义

重儿子：以结点的一个儿子为根的子树的结点个数中最大的那一个儿子称为重儿子。

轻儿子：除了重儿子以外的儿子。

重边：结点与其重儿子的边称为重边。

轻边：结点与其轻儿子的边称为轻边。

重链：由重边组成的路径。

轻链：由轻边组成的路径。

描述剖分后的树

描述结点:

siz[v]：以结点v为根的子树的结点个数

dep[v]：结点v的深度，定义根结点的深度为0

fa[v]：结点v的父亲结点

描述结点与路径之间的关系:

belong[v]：结点v所属的路径编号

idx[v]：结点v在其路径中的编号

son[v]：结点v的重儿子

描述路径：

top[p]：编号为p的路径的顶端结点

len[p]：路径p的长度

描述辅助数据结构：

sump[p]：路径p的编号

seg[v]：结点v的父边在线段树中的位置

wei[v]：结点v的父边的权值

剖分后的性质

如果 (u,v) 为轻边，则 siz[v] * 2 < siz[u]，即以轻儿子为根的子树中的结点数量相对少。

从根到某一点的路径上轻链、重链的个数都不大于 logn。

树链剖分的实现

首先用一次搜索求出 dep、fa、wei 的值，深搜广搜都可以，但是深搜容易爆栈，这里使用广搜。

在广搜的过程中得到了树的拓扑序，我们按照拓扑序的逆序遍历所有的结点。

在这个过程中可以求出 siz 与 son。

对于一个结点，如果它是叶子结点，那么我们就新建一条链，使该结点作为链上的第一个结点；

如果不是叶子结点，那么它与它的重儿子属于同一条链，对链进行更新即可。

1 void split(){ 2     memset(dep,-1,sizeof(dep)); 3     l=0; 4     dep[ que[r=1]=1 ]=0; // 将根结点插入队列，并设深度为0 5     fa[1]=-1; // 默认 1 为根结点 6     wei[1]=0; 7     while (l
         
          0;i--){22         int u=que[i],p=-1;23         siz[u]=1;24         son[u]=p;25         for (int k=head[u];k!=-1;k=edges[k].next){26             int v=edges[k].to;27             if (vis[v]){ // 若v是u的子结点28                 siz[u]+=siz[v]; // 计数29                 if (p==-1||siz[v]>siz[p]){30                     son[u]=v;31                     p=v; // u的重儿子是v32                 }33             }34         }35         if (p==-1){ // u是叶子结点36             idx[u]=len[++cnt]=1; // 一个新的路径编号为cnt，u是路径中的第一个结点37             belong[ top[cnt]=u ]=cnt; // u是顶端结点，且u属于路径cnt38         }39         else{ // u不是叶子结点40             idx[u]=++len[ belong[u]=belong[p] ]; // u属于重儿子所在的链，链长+1，u是路径中第len个结点41             top[ belong[u] ]=u; // u是顶端结点42         }43         vis[u]=true; // 访问标记44     }45 }

树链剖分

路径上的求和、求极值操作

我们对树上的边进行编号，编号对应着该边在线段树上的位置，保证同一个重链上的所有点的父边的编号是连续的即可。

这样我们就可以通过对线段树进行区间操作来快速的修改同一条重链上的权值了。

如图所示：

如何快速的处理任意两个结点 (va,vb) 间的边呢。

我们设 f1=top[belong[va]]，f2=top[belong[vb]]。表示 f1 是 va 所属的链上的最顶端的点， f2 是 vb 所属的链上的最顶端的点。

当 f1 != f2 时，若 dep[f1] >= dep[f2]，那么就处理 va 的父边到 f1 父边的路径，由于它们属于同一条重链的父边，编号是连续的，因此可以用线段树进行区间处理，最后使 va = fa[f1]，重复进行该步骤直到 f1=f2。

当 f1 = f2 时，va 与 vb 在同一条重链上，若 va 与 vb 不是同一点，就区间处理 va 到 vb 路径上的边，否则修改完成。

查询操作与修改操作是类似的。

例如要查找两个结点间路径上的权值最大的边：

1 int find(int va,int vb){ 2     int f1=top[belong[va]],f2=top[belong[vb]],tmp=0; 3     while (f1!=f2){ 4         if (dep[f1]
         
          dep[vb]) swap(va,vb);14     return max(tmp,tr.query(1,seg[son[va]],seg[vb]));15 }

查找路径上边权最大的边

相关练习题

SPOJ 375. Query on a tree

题目给出一棵含有n个结点的树，n-1条边每条边都有边权，有两种操作，修改第i条边的边权，查询两个结点的路径上最大的边权。

首先进行树链剖分，对边进行编号，建立线段树储存权值。

对于修改操作，我们找到该边在线段树上的位置然后单点更新即可。

对于查询操作，利用重链上的父边编号相同这一性质不断进行区间查询，就能快速找到最大的边权。

POJ 3237 Tree

与上一题相比多了一种操作，将两个结点间的边权取负。

用线段树维护两个值，区间上的最小值与最大值。区间取负时将最大值最小值取负后交换，打上延迟标记。

1 #include 
         
            2 #include 
          
             3 #include 
           
              4 #include 
            
               5   6 using namespace std;  7   8 const int maxn=101010+5;  9 const int maxm=maxn+maxn; 10  11 struct EDGENODE{ 12     int to; 13     int w; 14     int next; 15 }edges[maxm]; 16 int head[maxn],edge; 17 inline void init(){ 18     edge=0; 19     memset(head,-1,sizeof(head)); 20 } 21 inline void addedge(int u,int v,int w){ 22     edges[edge].w=w,edges[edge].to=v,edges[edge].next=head[u],head[u]=edge++; 23     edges[edge].w=w,edges[edge].to=u,edges[edge].next=head[v],head[v]=edge++; 24 } 25 int que[maxn]; // 队列 26 bool vis[maxn]; // 访问标记 27 int son[maxn]; // 重儿子 28 int idx[maxn]; // 结点v在其路径中的编号 29 int dep[maxn]; // 结点v的深度 30 int siz[maxn]; // 以结点v为根的子树的结点个数 31 int belong[maxn]; // 结点v所属的路径编号 32 int fa[maxn]; // 结点v的父亲结点 33 int top[maxn]; // 编号为p的路径的顶端结点 34 int len[maxn]; // 路径p的长度 35 int sump[maxn]; // 路径p的编号 36 int seg[maxn]; // 结点v的父边在线段树中的位置 37 int wei[maxn]; // 结点v的父边的权值 38 int l,r,ans,cnt; 39 int n; 40 char cmd[22]; 41  42 void split(){ 43     memset(dep,-1,sizeof(dep)); 44     l=0; 45     dep[ que[r=1]=1 ]=0; // 将根结点插入队列，并设深度为0 46     fa[1]=-1; // 默认 1 为根结点 47     wei[1]=0; 48     while (l
             
              0;i--){ 63         int u=que[i],p=-1; 64         siz[u]=1; 65         son[u]=p; 66         for (int k=head[u];k!=-1;k=edges[k].next){ 67             int v=edges[k].to; 68             if (vis[v]){ // 若v是u的子结点 69                 siz[u]+=siz[v]; // 计数 70                 if (p==-1||siz[v]>siz[p]){ 71                     son[u]=v; 72                     p=v; // u的重儿子是v 73                 } 74             } 75         } 76         if (p==-1){ // u是叶子结点 77             idx[u]=len[++cnt]=1; // 一个新的路径编号为cnt，u是路径中的第一个结点 78             belong[ top[cnt]=u ]=cnt; // u是顶端结点，且u属于路径cnt 79         } 80         else{ // u不是叶子结点 81             idx[u]=++len[ belong[u]=belong[p] ]; // u属于重儿子所在的链，链长+1，u是路径中第len个结点 82             top[ belong[u] ]=u; // u是顶端结点 83         } 84         vis[u]=true; // 访问标记 85     } 86 } 87 const int INF=0x3fffffff; 88 struct SegmentTree{ 89     int num[maxn]; 90     struct Tree{ 91         int l; 92         int r; 93         int max; 94         int min; 95         bool neg; 96     }; 97     Tree tree[maxn*4]; 98     void push_down(int root){ 99         if (tree[root].neg){100             if (tree[root].l!=tree[root].r){101                 tree[root<<1].neg^=1;102                 tree[root<<1|1].neg^=1;103                 swap(tree[root<<1].max,tree[root<<1].min);104                 swap(tree[root<<1|1].max,tree[root<<1|1].min);105                 tree[root<<1].max*=-1;106                 tree[root<<1].min*=-1;107                 tree[root<<1|1].max*=-1;108                 tree[root<<1|1].min*=-1;109             }110         }111         tree[root].neg=0;112     }113     void push_up(int root){114         tree[root].max=max(tree[root<<1].max,tree[root<<1|1].max);115         tree[root].min=min(tree[root<<1].min,tree[root<<1|1].min);116     }117     void build(int root,int l,int r){118         tree[root].l=l;119         tree[root].r=r;120         tree[root].neg=0;121         if(tree[root].l==tree[root].r){122             tree[root].max=num[l];123             tree[root].min=num[l];124             tree[root].neg=0;125             return;126         }127         int mid=(l+r)/2;128         build(root<<1,l,mid);129         build(root<<1|1,mid+1,r);130         push_up(root);131     }132     void update(int root,int pos,int val){133         if(tree[root].l==tree[root].r){134             tree[root].max=val;135             tree[root].min=val;136             return;137         }138         push_down(root);139         int mid=(tree[root].l+tree[root].r)/2;140         if(pos<=mid) update(root<<1,pos,val);141         else update(root<<1|1,pos,val);142         push_up(root);143     }144     int query(int root,int L,int R){145         if(L<=tree[root].l&&R>=tree[root].r) return tree[root].max;146         push_down(root);147         int mid=(tree[root].l+tree[root].r)/2,ret=-INF;148         if(L<=mid) ret=max(ret,query(root<<1,L,R));149         if(R>mid) ret=max(ret,query(root<<1|1,L,R));150         push_up(root);151         return ret;152     }153     void nega(int root,int L,int R){154         if (L<=tree[root].l&&R>=tree[root].r){155             tree[root].neg^=1;156             swap(tree[root].max,tree[root].min);157             tree[root].max*=-1;158             tree[root].min*=-1;159             return;160         }161         push_down(root);162         int mid=(tree[root].l+tree[root].r)/2;163         if (L<=mid) nega(root<<1,L,R);164         if (R>mid) nega(root<<1|1,L,R);165         push_up(root);166     }167     void debug(int root){168         printf("rt=%d, [%d~%d], min=%d, max=%d, neg=%d\n",root,tree[root].l,tree[root].r,tree[root].min,tree[root].max,(int)tree[root].neg);169         if (tree[root].l==tree[root].r) return;170         debug(root<<1);171         debug(root<<1|1);172     }173 }tr;174 175 int find(int va,int vb){176     int f1=top[belong[va]],f2=top[belong[vb]],tmp=-INF;177     while (f1!=f2){178         if (dep[f1]
              
               dep[vb]) swap(va,vb);188 return max(tmp,tr.query(1,seg[son[va]],seg[vb]));189 }190 void gao(int va,int vb){191 int f1=top[belong[va]],f2=top[belong[vb]];192 while (f1!=f2){193 if (dep[f1]
               
                dep[vb]) swap(va,vb);203 tr.nega(1,seg[son[va]],seg[vb]);204 }205 int d[maxn][3];206 207 int main()208 {209 int T;210 scanf("%d",&T);211 while (T--){212 init();213 scanf("%d",&n);214 for (int i=1;i