这几天学习了一下树链剖分,顺便写一下我的理解、
早上看了一下别人的讲解,云里雾里,终于算是搞懂了、
树链剖分是解决在树上进行插点问线,插线问点等一系列树上的问题
假如现在给你一棵树,然后没两条边之间有一条权值,有一些操作,1:x---y之间的最大权值是多少,2:改变x---y之间的权值
当前这样的操作有很多,如果直接用暴力的方法的话肯定不行,那么就要想一个好的方法,我们可以想一下能不能借助线段树解决,能不能想一种方法对树上的边进行编号,然后就变成区间了。那么我们就可以在线段树上进行操作了,树链剖分就是这样的一个算法。
当然编号不是简单的随便编号,如果我们进行随便的编号,然后建立一个线段树,如果要更新一个边的权值,是log2(n)的复杂度,而查找的话,我们要枚举x--y的之间的所有的边,假如我们随便以一个点为根节点进行编号,最大的长度是树的直径,这个值本身是比较大的,而在线段树上查找任意一个区间的复杂度也是log2(n),这样查找一次的时间复杂度比直接暴力还要高,所以很明显是不行的。
那么就要想想办法了,我们能不能把x--y之间的一些边一块儿查找,这就是关于树链剖分的重边和轻边,
重边:某个节点x到孩子节点形成的子树中节点数最多的点child之间的边,由定义发现除了叶子节点其他节点只有一条重边
重边是可以放在一块儿更新的,而有
性质:从根到某一点的路径上轻边、重边的个数都不大于logn。
所以这样查找的时间复杂度相当于log2(n)
其实树链剖分就是把边哈希到线段树上的数据结构。
实现的话很简单,用两个dfs处理数数的信息,重边以及轻边,然后就是一些线段树的操作了。
模板“:以spoj 375 为例
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 }