树链剖分详解及模板

这几天学习了一下树链剖分，顺便写一下我的理解、

早上看了一下别人的讲解，云里雾里，终于算是搞懂了、

树链剖分是解决在树上进行插点问线，插线问点等一系列树上的问题

假如现在给你一棵树，然后没两条边之间有一条权值，有一些操作，1：x---y之间的最大权值是多少，2：改变x---y之间的权值

当前这样的操作有很多，如果直接用暴力的方法的话肯定不行，那么就要想一个好的方法，我们可以想一下能不能借助线段树解决，能不能想一种方法对树上的边进行编号，然后就变成区间了。那么我们就可以在线段树上进行操作了，树链剖分就是这样的一个算法。

当然编号不是简单的随便编号，如果我们进行随便的编号，然后建立一个线段树，如果要更新一个边的权值，是log2（n）的复杂度，而查找的话，我们要枚举x--y的之间的所有的边，假如我们随便以一个点为根节点进行编号，最大的长度是树的直径，这个值本身是比较大的，而在线段树上查找任意一个区间的复杂度也是log2（n），这样查找一次的时间复杂度比直接暴力还要高，所以很明显是不行的。

那么就要想想办法了，我们能不能把x--y之间的一些边一块儿查找，这就是关于树链剖分的重边和轻边，

重边：某个节点x到孩子节点形成的子树中节点数最多的点child之间的边，由定义发现除了叶子节点其他节点只有一条重边

重边是可以放在一块儿更新的，而有

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

所以这样查找的时间复杂度相当于log2（n）

其实树链剖分就是把边哈希到线段树上的数据结构。

实现的话很简单，用两个dfs处理数数的信息，重边以及轻边，然后就是一些线段树的操作了。

模板“：以spoj 375 为例

[cpp] view plain copy

print?

1. #include <cstdio>  
2. #include <cstring>  
3. #include <vector>  
4. #include <algorithm>  
5. using namespace std;  
6. #define Del(a,b) memset(a,b,sizeof(a))  
7. const int N = 10005;  
8.   
9. int dep[N],siz[N],fa[N],id[N],son[N],val[N],top[N]; //top 最近的重链父节点  
10. int num;  
11. vector<int> v[N];  
12. struct tree  
13. {  
14.     int x,y,val;  
15.     void read(){  
16.         scanf("%d%d%d",&x,&y,&val);  
17.     }  
18. };  
19. tree e[N];  
20. void dfs1(int u, int f, int d) {  
21.     dep[u] = d;  
22.     siz[u] = 1;  
23.     son[u] = 0;  
24.     fa[u] = f;  
25.     for (int i = 0; i < v[u].size(); i++) {  
26.         int ff = v[u][i];  
27.         if (ff == f) continue;  
28.         dfs1(ff, u, d + 1);  
29.         siz[u] += siz[ff];  
30.         if (siz[son[u]] < siz[ff])  
31.             son[u] = ff;  
32.     }  
33. }  
34. void dfs2(int u, int tp) {  
35.     top[u] = tp;  
36.     id[u] = ++num;  
37.     if (son[u]) dfs2(son[u], tp);  
38.     for (int i = 0; i < v[u].size(); i++) {  
39.         int ff = v[u][i];  
40.         if (ff == fa[u] || ff == son[u]) continue;  
41.         dfs2(ff, ff);  
42.     }  
43. }  
44. #define lson(x) ((x<<1))  
45. #define rson(x) ((x<<1)+1)  
46. struct Tree  
47. {  
48.     int l,r,val;  
49. };  
50. Tree tree[4*N];  
51. void pushup(int x) {  
52.     tree[x].val = max(tree[lson(x)].val, tree[rson(x)].val);  
53. }  
54.   
55. void build(int l,int r,int v)  
56. {  
57.     tree[v].l=l;  
58.     tree[v].r=r;  
59.     if(l==r)  
60.     {  
61.         tree[v].val = val[l];  
62.         return ;  
63.     }  
64.     int mid=(l+r)>>1;  
65.     build(l,mid,v*2);  
66.     build(mid+1,r,v*2+1);  
67.     pushup(v);  
68. }  
69. void update(int o,int v,int val)  //log(n)  
70. {  
71.     if(tree[o].l==tree[o].r)  
72.     {  
73.         tree[o].val = val;  
74.         return ;  
75.     }  
76.     int mid = (tree[o].l+tree[o].r)/2;  
77.     if(v<=mid)  
78.         update(o*2,v,val);  
79.     else  
80.         update(o*2+1,v,val);  
81.     pushup(o);  
82. }  
83. int query(int x,int l, int r)  
84. {  
85.     if (tree[x].l >= l && tree[x].r <= r) {  
86.         return tree[x].val;  
87.     }  
88.     int mid = (tree[x].l + tree[x].r) / 2;  
89.     int ans = 0;  
90.     if (l <= mid) ans = max(ans, query(lson(x),l,r));  
91.     if (r > mid) ans = max(ans, query(rson(x),l,r));  
92.     return ans;  
93. }  
94.   
95. int Yougth(int u, int v) {  
96.     int tp1 = top[u], tp2 = top[v];  
97.     int ans = 0;  
98.     while (tp1 != tp2) {  
99.         //printf("YES\n");  
100.         if (dep[tp1] < dep[tp2]) {  
101.             swap(tp1, tp2);  
102.             swap(u, v);  
103.         }  
104.         ans = max(query(1,id[tp1], id[u]), ans);  
105.         u = fa[tp1];  
106.         tp1 = top[u];  
107.     }  
108.     if (u == v) return ans;  
109.     if (dep[u] > dep[v]) swap(u, v);  
110.     ans = max(query(1,id[son[u]], id[v]), ans);  
111.     return ans;  
112. }  
113. void Clear(int n)  
114. {  
115.     for(int i=1;i<=n;i++)  
116.         v[i].clear();  
117. }  
118. int main()  
119. {  
120.     //freopen("Input.txt","r",stdin);  
121.     int T;  
122.     scanf("%d",&T);  
123.     while(T--)  
124.     {  
125.         int n;  
126.         scanf("%d",&n);  
127.         for(int i=1;i<n;i++)  
128.         {  
129.             e[i].read();  
130.             v[e[i].x].push_back(e[i].y);  
131.             v[e[i].y].push_back(e[i].x);  
132.         }  
133.         num = 0;  
134.         dfs1(1,0,1);  
135.         dfs2(1,1);  
136.         for (int i = 1; i < n; i++) {  
137.             if (dep[e[i].x] < dep[e[i].y]) swap(e[i].x, e[i].y);  
138.             val[id[e[i].x]] = e[i].val;  
139.         }  
140.         build(1,num,1);  
141.         char s[200];  
142.         while(~scanf("%s",&s) && s[0]!='D')  
143.         {  
144.             int x,y;  
145.             scanf("%d%d",&x,&y);  
146.             if(s[0]=='Q')  
147.                 printf("%d\n",Yougth(x,y));  
148.             if (s[0] == 'C')  
149.                 update(1,id[e[x].x],y);  
150.         }  
151.         Clear(n);  
152.     }  
153.     return 0;  
154. }  

树链剖分用一句话概括就是：把一棵树剖分为若干条链，然后利用数据结构(树状数组，SBT，Splay，线段树等等)去维护每一

条链，复杂度为O(logn)

 

 

那么，树链剖分的第一步当然是对树进行轻重边的划分。

定义size(x)为以x为根的子树节点个数，令v为u的儿子中size值最大的节点，那么(u,v)就是重边，其余边为轻边。

 

当然，关于这个它有两个重要的性质：

(1)轻边(u,v)中，size(v)<=size(u/2)

(2)从根到某一点的路径上，不超过logn条轻边和不超过logn条重路径。

 

 

当然，剖分过程分为两次dfs，或者bfs也可以。

 

如果是两次dfs，那么第一次dfs就是找重边，也就是记录下所有的重边。

然后第二次dfs就是连接重边形成重链，具体过程就是：以根节点为起点，沿着重边向下拓展，拉成重链，不在当前重链上的节

点，都以该节点为起点向下重新拉一条重链。

 

 

剖分完毕后，每条重链相当于一段区间，然后用数据结构去维护，把所有重链首尾相接，放到数据结构上，然后维护整体。

 

在这里，当然有很多数组，现在我来分别介绍它们的作用：

 

siz[]数组，用来保存以x为根的子树节点个数

top[]数组，用来保存当前节点的所在链的顶端节点

son[]数组，用来保存重儿子

dep[]数组，用来保存当前节点的深度

fa[]数组，用来保存当前节点的父亲

tid[]数组，用来保存树中每个节点剖分后的新编号

rank[]数组，用来保存当前节点在线段树中的位置

 

那么，我们现在可以根据描述给出剖分的代码：

第一次dfs：记录所有的重边

void dfs1(int u,int father,int d)
{
    dep[u]=d;
    fa[u]=father;
    siz[u]=1;
    for(int i=head[u];~i;i=next[i])
    {
        int v=to[i];
        if(v!=father)
        {
            dfs1(v,u,d+1);
            siz[u]+=siz[v];
            if(son[u]==-1||siz[v]>siz[son[u]])
                son[u]=v;
        }
    }
}

第二次dfs：连重边成重链

void dfs2(int u,int tp)
{
    top[u]=tp;
    tid[u]=++tim;
    rank[tid[u]]=u;
    if(son[u]==-1) return;
    dfs2(son[u],tp);
    for(int i=head[u];~i;i=next[i])
    {
        int v=to[i];
        if(v!=son[u]&&v!=fa[u])
            dfs2(v,v);
    }
}

当然，由于题目有时候要求边很多，所以最好不要用二维数组表示边，应用邻接表或者链式前向星。

 

 

当然，这里面有一个重要的操作，那就是修改树中边权的值。

 

如何修改u到v的边权的值呢？这里有两种情况：

(1)如果u与v在同一条重链上，那么就直接修改了

(2)如果u与v不在同一条重链上，那么就一边进行修改，一边将u与v往同一条重链上靠，这样就变成了第一种情况了

 

那么现在的关键问题就是如何将u和v往同一条重链上靠？这个问题此处我就省略了。