首页 > 代码库 > hdu-3699-Aragorn's Story-樹鏈剖分模板題
hdu-3699-Aragorn's Story-樹鏈剖分模板題
樹鏈剖分學習blog：http://blog.csdn.net/jiangshibiao/article/details/24669751
關於這題的學習blog：http://blog.csdn.net/acdreamers/article/details/10594121
下面來說說樹鏈剖分の我的理解。
作為一個樹鏈剖分的初學者，看到個大牛的博客里一上來就描述做法，稍顯得有點吃不消，嚼了好幾天的資料才總算看懂。作為一個初學者，以初學的狀態，透過現象看本質才能更好地上手，因為只有知道它能做什麼，才會順著思考怎麼做，才能更順利地轉化成自己的代碼思路。
按我的理解，樹鏈剖分準確來說不是一種數據結構，只是一種思想罷了，做過 poj3321、和 hdu3333之類的題或許會更有感觸，樹鏈剖分也只是像dfs序一樣，用一種方法將一棵樹更好地編碼（不管是邊或節點）然後用別的數據結構高效維護。
下面講講實現，由於我目前只寫了關於點的剖分（還有剖分邊的），所以以下以節點的剖分做講解，維護用線段樹（這裡默認你懂線段樹了）。
樹鏈剖分也叫輕重鏈剖分，即是把一棵樹按子節點的孩子個數分為輕重鏈，父節點下的兒子數目多的節點為重兒子，其餘的都為輕兒子。標註dfs序的時候，我們先標註完重鏈（都是重兒子組成的鏈）上的點，再標註輕鏈，這樣，對於一條重鏈，其節點在線段樹中的排列是連續的。我們在查詢的時候，如果節點在同一條重鏈上，即可直接查詢。到這裡，用兩個dfs預處理完， 就完成了對一棵樹的剖分了。具體實現請轉上面的blog。就不重複造輪子了。
接著是修改查詢操作。修改一條樹上的路徑，由上預處理操作我們可以知識遷移一下，對於在同一條重鏈里的路徑，我們可以按dfs出來的映射直接在線段樹中修改；如果不在同一重鏈，由於樹上的路徑唯一，我們可以從更深的節點開始往上修改，直到兩者在一條鏈（也可能是一個點）中，即是修改更深的節點所在的重鏈（如果節點是輕邊上的葉子節點，則修改的只是它自己）然後將節點賦值為該重鏈的父親節點，重複操作直到兩點在同一重鏈（這裡用到dfs求出的top[]——重鏈首節點、fa[]——節點的直接父節點，父親節點和重鏈首節點連的是一條輕邊，自己想想為什麼，其實畫畫圖就知道了）。對於查詢也是同理。但是杭電這道3699由於是單點查詢，所以省了好多麻煩。
對於樹鏈剖分的分析就到這了，實現請移步上面的blog，在做之前最好自己摸清思路，按照作者思路先實現一遍再看別人代碼，這才能更好地發現自己思維上的不足。
講完之後，這道題實際上就是一道水水的模板題辣。
AC代碼：
1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 const int maxn = 50010; 8 int son[maxn], deep[maxn], num[maxn], tree[maxn], pre[maxn], fa[maxn], top[maxn]; 9 int to[maxn<<1], next[maxn<<1], head[maxn]; 10 int n, m, p, edge, cnt, arr[maxn]; 11 void add(int a, int b) //数组模拟邻接表存图 12 { 13 to[edge] = b; next[edge] = head[a]; head[a] = edge++; 14 } 15 void init() 16 { 17 edge = 0; 18 cnt = 0; 19 top[1] = 1; deep[1] = 1; num[1] = 1; fa[1] = 1; 20 memset(head, -1, sizeof(head)); 21 memset(son, -1, sizeof(son)); 22 } 23 void dfs1(int u) 24 { 25 num[u] = 1; 26 for(int e = head[u]; ~e; e = next[e]){ 27 int too = to[e]; 28 if(too != fa[u]) { 29 fa[too] = u; deep[too] = deep[u]+1; 30 dfs1(too); 31 num[u] += num[too]; //儿子数 32 if(son[u] == -1||num[too] > num[son[u]]) son[u] = too; //son[u]存u的重儿子节点编号 33 } 34 } 35 } 36 void dfs2(int u, int lead) 37 { 38 top[u] = lead; //重链的链首节点 39 tree[u] = ++cnt; //tree存线段树中节点编号 40 pre[tree[u]] = u; //pre存线段树编号对应的树节点编号 41 if(son[u] == -1) return; 42 dfs2(son[u], lead); 43 for(int e = head[u]; ~e; e = next[e]) { 44 int too = to[e]; 45 if(son[u] != too&&fa[u] != too) dfs2(too, too); 46 } 47 } 48 49 #define lson l, m, rt<<1 50 #define rson m+1, r, rt<<1|1 51 int sgt[maxn<<2], lazy[maxn<<2]; //以下是线段树 52 void push_down(int rt) 53 { 54 if(lazy[rt] != 0) { 55 lazy[rt<<1] += lazy[rt]; 56 lazy[rt<<1|1] += lazy[rt]; 57 lazy[rt] = 0; 58 } 59 } 60 void build(int l, int r, int rt) 61 { 62 lazy[rt] = 0; sgt[rt] = 0; 63 if(l == r) { 64 sgt[rt] = arr[pre[l]]; 65 return ; 66 } 67 int m = (l+r)>>1; 68 build(lson); build(rson); 69 } 70 void update(int l, int r, int rt, int L, int R, int val) 71 { 72 if(L <= l && r <= R) { 73 lazy[rt] += val; 74 return; 75 } 76 push_down(rt); 77 int m = (l+r)>>1; 78 if(L <= m) update(lson, L, R, val); 79 if(m < R) update(rson, L, R, val); 80 } 81 void change(int L, int R, int val) 82 { 83 while(top[L] != top[R]) { //直到在同一链中 84 if(deep[top[L]] < deep[top[R]]) swap(L, R); //先处理更深的节点 85 update(1, n, 1, tree[top[L]], tree[L], val); 86 L = fa[top[L]]; 87 } 88 if(deep[L] > deep[R]) swap(L, R); 89 update(1, n, 1, tree[L], tree[R], val); 90 } 91 int query(int l, int r, int rt, int pos) 92 { 93 if(l == r) { 94 sgt[rt] += lazy[rt]; 95 lazy[rt] = 0; 96 return sgt[rt]; 97 } 98 push_down(rt); 99 int m = (l+r)>>1;100 int res;101 if(pos <= m) res = query(lson, pos);102 else res = query(rson, pos);103 return res;104 }105 int main()106 {107 while(scanf("%d%d%d", &n, &m, &p) != EOF) {108 init();109 for(int i = 1; i <= n; i++) {110 scanf("%d", &arr[i]);111 }112 for(int i = 0; i < m ;i++) {113 int a, b;114 scanf("%d%d", &a, &b);115 add(a, b); add(b, a);116 }117 dfs1(1);118 dfs2(1, 1);119 build(1, n, 1);120 while(p--) {121 char s[3]; int c1, c2, k;122 scanf("%s%d", s, &c1);123 if(s[0] == ‘Q‘) {124 printf("%d\n", query(1, n, 1, tree[c1]));125 }126 else {127 scanf("%d%d", &c2, &k);128 if(s[0] == ‘D‘) k = -k;129 change(c1, c2, k);130 }131 }132 }133 return 0;134 }
hdu-3699-Aragorn's Story-樹鏈剖分模板題