首页 > 代码库 > 树链剖分
树链剖分
什么是树链剖分
树链剖分并不是一个复杂的算法或者数据结构，它能把一棵树拆成链。
树链，就是树上的路径。剖分，就是把路径分类为重链和轻链。
给定一棵树，将它划分成若干条互不相交的路径，满足：从节点 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<r){ // 第一遍搜索求出 fa,dep,wei 8 int u=que[++l]; 9 vis[u]=false; // 顺便初始化vis10 for (int i=head[u];i!=-1;i=edges[i].next){11 int v=edges[i].to;12 int w=edges[i].w;13 if (dep[v]==-1){ // 未访问过的结点14 dep[ que[++r]=v ]=dep[u]+1; // 将v插入队列并设深度为dep[u]+115 fa[v]=u; // v的父结点为u16 wei[v]=w; // v的父边权值17 }18 }19 }20 cnt=0; // 重链编号21 for (int i=n;i>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[f2]){ 5 swap(f1,f2); 6 swap(va,vb); 7 } 8 tmp=max(tmp,tr.query(1,seg[f1],seg[va])); 9 va=fa[f1];10 f1=top[belong[va]];11 }12 if (va==vb) return tmp;13 if (dep[va]>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 <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 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<r){ // 第一遍搜索求出 fa,dep,wei 49 int u=que[++l]; 50 vis[u]=false; // 顺便初始化vis 51 for (int i=head[u];i!=-1;i=edges[i].next){ 52 int v=edges[i].to; 53 int w=edges[i].w; 54 if (dep[v]==-1){ // 未访问过的结点 55 dep[ que[++r]=v ]=dep[u]+1; // 将v插入队列并设深度为dep[u]+1 56 fa[v]=u; // v的父结点为u 57 wei[v]=w; // v的父边权值 58 } 59 } 60 } 61 cnt=0; // 重链编号 62 for (int i=n;i>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[f2]){179 swap(f1,f2);180 swap(va,vb);181 }182 tmp=max(tmp,tr.query(1,seg[f1],seg[va]));183 va=fa[f1];184 f1=top[belong[va]];185 }186 if (va==vb) return tmp;187 if (dep[va]>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[f2]){194 swap(f1,f2);195 swap(va,vb);196 }197 tr.nega(1,seg[f1],seg[va]);198 va=fa[f1];199 f1=top[belong[va]];200 }201 if (va==vb) return;202 if (dep[va]>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<n;i++){215 int a,b,c;216 scanf("%d%d%d",&a,&b,&c);217 d[i][0]=a;218 d[i][1]=b;219 d[i][2]=c;220 addedge(a,b,c);221 }222 split();223 sump[0]=0;224 for (int i=1;i<=cnt;i++) sump[i]=sump[i-1]+len[i];225 for (int i=1;i<=n;i++){226 seg[i]=sump[ belong[i] ]-idx[i]+1;227 tr.num[ seg[i] ]=wei[i];228 }229 tr.build(1,1,n);230 while (scanf("%s",cmd)){231 if (cmd[0]==‘D‘) break;232 int x,y;233 scanf("%d%d",&x,&y);234 if (cmd[0]==‘Q‘){235 printf("%d\n",find(x,y));236 }237 if (cmd[0]==‘C‘){238 if (fa[d[x][1]]==d[x][0]) tr.update(1,seg[d[x][1]],y);239 else tr.update(1,seg[d[x][0]],y);240 }241 if (cmd[0]==‘N‘){242 gao(x,y);243 }244 }245 }246 return 0;247 }248 249 /**250 1251 10252 1 2 1253 2 3 3254 3 4 8255 4 5 -6256 5 6 -9257 6 7 -1258 7 8 1259 8 9 7260 9 10 6261 NEGATE 1 8262 CHANGE 2 7263 QUERY 1 3264 NEGATE 1 5265 CHANGE 4 7266 QUERY 3 5267 DONE268 269 3270 10271 1 2 1272 2 3 7273 3 4 8274 4 5 6275 5 6 9276 6 7 1277 7 8 1278 8 9 7279 9 10 6280 NEGATE 4 7281 CHANGE 2 3282 QUERY 2 9283 CHANGE 2 3284 QUERY 6 8285 NEGATE 1 8286 CHANGE 2 7287 QUERY 1 3288 NEGATE 1 5289 CHANGE 4 7290 QUERY 3 5291 DONE292 6293 1 2 1294 2 3 2295 3 4 4296 4 5 100297 5 6 -1000298 QUERY 1 2299 CHANGE 1 3300 QUERY 1 2301 NEGATE 1 2302 QUERY 1 3303 QUERY 1 2304 CHANGE 1 10305 QUERY 1 3306 NEGATE 1 2307 QUERY 1 3308 CHANGE 1 10309 CHANGE 2 20310 QUERY 1 3311 NEGATE 1 2312 QUERY 1 3313 NEGATE 2 3314 QUERY 1 3315 CHANGE 1 -100316 CHANGE 2 -1000317 QUERY 1 4318 NEGATE 1 6319 QUERY 1 6320 DONE321 100322 1 2 265323 2 3 133324 3 4 508325 4 5 197326 5 6 437327 6 7 849328 7 8 577329 8 9 503330 9 10 478331 10 11 434332 11 12 877333 12 13 691334 13 14 54335 14 15 295336 15 16 421337 16 17 166338 17 18 550339 18 19 410340 19 20 868341 20 21 476342 21 22 283343 22 23 410344 23 24 915345 24 25 308346 25 26 301347 26 27 553348 27 28 609349 28 29 733350 29 30 770351 30 31 635352 31 32 581353 32 33 753354 33 34 707355 34 35 448356 35 36 738357 36 37 841358 37 38 389359 38 39 532360 39 40 210361 40 41 458362 41 42 595363 42 43 989364 43 44 678365 44 45 214366 45 46 746367 46 47 548368 47 48 117369 48 49 758370 49 50 437371 50 51 840372 51 52 555373 52 53 726374 53 54 490375 54 55 719376 55 56 403377 56 57 329378 57 58 92379 58 59 311380 59 60 664381 60 61 207382 61 62 170383 62 63 548384 63 64 713385 64 65 556386 65 66 705387 66 67 82388 67 68 508389 68 69 59390 69 70 45391 70 71 670392 71 72 540393 72 73 826394 73 74 262395 74 75 504396 75 76 989397 76 77 408398 77 78 896399 78 79 388400 79 80 15401 80 81 485402 81 82 219403 82 83 977404 83 84 641405 84 85 985406 85 86 189407 86 87 64408 87 88 641409 88 89 320410 89 90 788411 90 91 441412 91 92 785413 92 93 163414 93 94 153415 94 95 852416 95 96 36417 96 97 10418 97 98 145419 98 99 956420 99 100 641421 QUERY 32 69422 NEGATE 1 22423 CHANGE 40 53424 QUERY 17 38425 NEGATE 17 65426 CHANGE 49 68427 QUERY 44 52428 NEGATE 11 53429 CHANGE 9 68430 QUERY 2 49431 NEGATE 25 45432 CHANGE 23 67433 QUERY 89 90434 NEGATE 5 37435 CHANGE 27 53436 QUERY 22 86437 NEGATE 6 7438 CHANGE 17 23439 QUERY 78 93440 NEGATE 30 63441 CHANGE 56 99442 QUERY 3 29443 NEGATE 24 38444 CHANGE 9 95445 QUERY 63 66446 NEGATE 69 92447 CHANGE 9 91448 QUERY 7 27449 NEGATE 32 60450 CHANGE 48 77451 QUERY 47 94452 NEGATE 14 27453 CHANGE 50 99454 QUERY 38 97455 NEGATE 11 67456 CHANGE 74 83457 QUERY 28 81458 NEGATE 13 53459 CHANGE 55 88460 QUERY 2 66461 NEGATE 71 95462 CHANGE 32 74463 QUERY 14 50464 NEGATE 1 28465 CHANGE 16 80466 QUERY 36 75467 NEGATE 20 49468 CHANGE 22 54469 QUERY 5 46470 NEGATE 12 37471 CHANGE 61 94472 QUERY 18 92473 NEGATE 19 26474 CHANGE 6 94475 QUERY 33 60476 NEGATE 79 87477 CHANGE 30 75478 QUERY 55 94479 NEGATE 28 79480 CHANGE 23 31481 QUERY 91 95482 NEGATE 28 76483 CHANGE 8 41484 QUERY 6 25485 NEGATE 19 70486 CHANGE 17 54487 QUERY 52 66488 NEGATE 4 95489 CHANGE 19 52490 QUERY 73 87491 DONE492 493 494 **/
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。