首先了解一下基本概念：
重儿子：siz[u]为v的子节点中siz值最大的，那么u就是v的重儿子。
轻儿子：v的其它子节点。 重边：点v与其重儿子的连边。 轻边：点v与其轻儿子的连边。 重链：由重边连成的路径。 轻链：轻边。 剖分后的树有如下性质： 性质1：如果(v,u)为轻边，则siz[u] * 2 < siz[v]； 性质2：从根到某一点的路径上轻链、重链的个数都不大于logN。树链剖分，如其字面意思，就是将一棵树按照轻重边剖分为多条链，使得每个节点都属于一条重链，然后按照某种顺序将链依次连接成一维结构，再通过线段树、树状数组、Splay等维护这条长链上的每一条链。
由于重链的个数是O(logN)的，而每条链上的操作也是O(logN)的，故一次树上路径的操作的花费为O(log²N)。
模板：
题目输入输出要求：N个点，M（M=N-1）条边，K个操作
N个点的值
M行 （u, v）边
K个操作，I （或D）a b c：a~b路径上的点值加（或减）c，Q a：a节点的值
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #pragma comment(linker, "/STACK:102400000,102400000") 9 using namespace std; 10 11 const int N = 50010, M = N * 2; 12 const int inf = 0x3f3f3f3f; 13 /*=============================================================*/ 14 /** 建树 */ 15 struct EG { 16 int u, v; 17 EG(){} 18 EG(int u, int v) : u(u), v(v) {} 19 } eg[M]; 20 int first[N], Next[M]; 21 int tot; 22 void init() 23 { 24 tot = 0; 25 memset(first, -1, sizeof(first)); 26 } 27 void add_edge(int u, int v) 28 { 29 eg[++tot] = EG(u, v); 30 Next[tot] = first[u], first[u] = tot; 31 eg[++tot] = EG(v, u); 32 Next[tot] = first[v], first[v] = tot; 33 } 34 35 /*=============================================================*/ 36 37 int fa[N], son[N], dep[N], dfn[N], top[N], sz[N], Rank[N], d[N]; 38 int tim; 39 /** 以DFS序遍历整棵树并获得如下信息： 40 sz[u] : 以u为根节点的子树的结点个数，是判断重儿子的依据 41 son[u]: 重儿子 42 dep[u]: u节点的深度 43 fa[u]: u节点的父节点 44 */ 45 void DFS1(int u) 46 { 47 sz[u] = 1; 48 son[u] = -1; 49 for(int i=first[u]; i!=-1; i=Next[i]) 50 { 51 EG &e = eg[i]; 52 if(e.v == fa[u]) continue; 53 dep[e.v] = dep[u] + 1; 54 fa[e.v] = u; 55 DFS1(e.v); 56 sz[u] += sz[e.v]; 57 if(son[u]==-1 || sz[son[u]] < sz[e.v]) 58 son[u] = e.v; 59 } 60 } 61 62 /** 63 将上面产生的重链串起来，生成Rank[]和dfn[]数组。 64 top[u]: u节点所在链的顶端节点 65 dfn[u]: u节点的DFS时间戳，各个重链是按照时间戳的先后形成的，也就是说，线段树、树状数组维护的数列是由时间戳从小到大一次形成的 66 Rank[t]: 时间戳为t的节点 67 */ 68 void DFS2(int u, int tp) 69 { 70 top[u] = tp; 71 dfn[u] = ++tim; 72 Rank[tim] = u; 73 if(son[u] == -1) return; 74 DFS2(son[u], tp); 75 for(int i=first[u]; i!=-1; i=Next[i]) 76 { 77 EG &e = eg[i]; 78 if(e.v != fa[u] && e.v != son[u]) 79 DFS2(e.v, e.v); 80 } 81 } 82 83 /** 线段树改段求点模板 */ 84 int mak[N<<2]; 85 void build(int l, int r, int rt) 86 { 87 mak[rt] = 0; 88 if(l == r) { 89 mak[rt] += d[Rank[l]]; 90 return; 91 } 92 int m = l + r >> 1; 93 build(l, m, rt<<1); 94 build(m+1, r, rt<<1|1); 95 } 96 97 void update(int L, int R, int a, int l, int r, int rt) 98 { 99 if(L <= l && R >= r) {100 mak[rt] += a;101 return;102 }103 int m = l + r >> 1;104 if(L <= m) update(L, R, a, l, m, rt<<1);105 if(R > m) update(L, R, a, m+1, r, rt<<1|1);106 }107 108 void query(int pos, int &a, int l, int r, int rt)109 {110 a += mak[rt];111 if(l == r)112 return;113 int m = l + r >> 1;114 if(pos <= m) query(pos, a, l, m, rt<<1);115 else query(pos, a, m+1, r, rt<<1|1);116 }117 118 /*==========================================================*/119 120 /** 操作树结构上在u、v路径上的节点*/121 void Update(int u, int v, int a, int n)122 {123 while(top[u] != top[v]) //当u、v节点不在同一条链上124 {125 //避免分类讨论，让u代表所在链顶较低的点126 if(dep[top[u]] < dep[top[v]]) swap(u, v);127 //top[u]~u这段路径在同一条重链上，其时间戳连续，更新之128 update(dfn[top[u]], dfn[u], a, 1, n, 1);129 130 //向上挑至链顶的父节点131 /*为什么是向上跳呢？132 因为v点所在链的顶端高于（或就是）u点所在链的顶端，无论哪种情况，v点所在链的顶端点的父节点在u~v链上*/133 u = fa[top[u]];134 }135 //此时，u、v在同一条链上，甚至u=v136 //重链上的节点，随着向子孙延伸，时间戳是递增的，即数列序是递增的137 if(dep[u] > dep[v]) swap(u, v);138 update(dfn[u], dfn[v], a, 1, n, 1);139 }140 141 /*==========================================================*/142 143 int main()144 {145 int n, m, k;146 while(scanf("%d %d %d", &n, &m, &k) == 3)147 {148 for(int i=1; i<=n; i++) scanf("%d", d+i);149 int a, b, c;150 init();151 for(int i=1; i<=m; i++)152 scanf("%d %d", &a, &b), add_edge(a,b);153 char s[3];154 dep[1] = 0;155 fa[1] = 1;156 tim = 0;157 DFS1(1);158 DFS2(1, 1);159 build(1, n, 1);160 while(k--)161 {162 scanf("%s", s);163 if(s[0] == 'Q') {164 scanf("%d", &a);165 b = 0;166 query(dfn[a], b, 1, n, 1);167 printf("%d\n", b);168 }169 else {170 scanf("%d %d %d", &a, &b, &c);171 Update(a, b, s[0]=='I' ? c : -c, n);172 }173 }174 }175 return 0;176 }