一 题目
二 分析
第一道树链剖分的题，写的好艰难啊。
题意还是比较好理解的，就是在树上操作。
对于修改，题中要求的是单点修改，就算是直接树上操作也是非常简单的。
对于查询，查询的时候，是查询树上一个结点到另一个结点的这条链上的最大值。这里就需要用树链剖分了。
树链剖分，其实就是把树型转换为线型的一种思想。通过剖分一棵树，可以得到很多的链，这些链保证了，树上的相邻节点在链中也一定是相邻的，这样，我们在操作的时候，就可以看做是对链进行更细致的操作了。对链操作时，还要将转换成的线性结构用线段树来维护，单点修改的同时保证快速求出最大值。
代码可以分为两部分，第一部分是树链剖分部分，第二部分就是线段树了（于普通线段树没有什么区别）。
三 AC代码
1 #include2 3 using namespace std; 4 5 const int MAXN = 1e5 + 15; 6 int N; 7 int e[MAXN][3]; 8 //临接链表建图 9 //双向的！ 10 struct Edge 11 { 12 int to, next; 13 }edge[MAXN*2]; 14 int head[MAXN], tot; 15 16 int fa[MAXN]; //父节点 17 int size[MAXN]; //以节点为根的子数大小 18 int deep[MAXN]; //深度 19 int son[MAXN]; //重儿子 20 int top[MAXN]; //重链的最高点 21 int p[MAXN]; //结点在整棵树中的编号 22 int fp[MAXN]; //p的反向 23 int pos; 24 25 void init() 26 { 27 tot = 0, pos = 0; 28 memset(head, -1, sizeof(head)); 29 memset(son, -1, sizeof(son)); 30 } 31 32 void addedge(int u, int v) 33 { 34 edge[tot].to = v; 35 edge[tot].next = head[u]; 36 head[u] = tot++; 37 } 38 39 void dfs1(int u, int pre, int d) 40 { 41 deep[u] = d; 42 fa[u] = pre; 43 size[u] = 1; 44 for(int i = head[u]; i != -1; i = edge[i].next) 45 { 46 int v = edge[i].to; 47 //因为建的是双向图 48 if(v != pre) 49 { 50 dfs1(v, u, d+1); 51 size[u] += size[v]; 52 if(son[u] == -1 || size[v] > size[son[u]]) 53 son[u] = v; 54 } 55 } 56 } 57 58 void dfs2(int u, int sp) 59 { 60 top[u] = sp; 61 62 if(son[u] != -1) 63 { 64 p[u] = pos++; 65 //血的教训把fp写成了fa!!! 66 fp[p[u]] = u; 67 dfs2(son[u], sp); 68 } 69 else 70 { 71 p[u] = pos++; 72 fp[p[u]] = u; 73 return; 74 } 75 76 for(int i = head[u]; i != -1; i = edge[i].next) 77 { 78 int v = edge[i].to; 79 if(v != son[u] && v != fa[u]) 80 dfs2(v, v); 81 } 82 } 83 84 struct Node 85 { 86 int l, r, Max; 87 }segTree[MAXN*3]; 88 89 void build(int rt, int l, int r) 90 { 91 segTree[rt].l = l; 92 segTree[rt].r = r; 93 segTree[rt].Max = 0; 94 if(l == r) return; 95 int mid = (l + r) >> 1; 96 build(rt<<1, l, mid); 97 build(rt<<1|1, mid + 1, r); 98 } 99 100 void push_up(int rt)101 {102 segTree[rt].Max = max(segTree[rt<<1].Max, segTree[rt<<1|1].Max);103 }104 105 void update(int rt, int k, int val)106 {107 if(segTree[rt].l == segTree[rt].r)108 {109 segTree[rt].Max = val;110 return;111 }112 int mid = (segTree[rt].l + segTree[rt].r) >> 1;113 if(k <= mid)114 update(rt<<1, k, val);115 else116 update(rt<<1|1, k, val);117 push_up(rt);118 }119 120 int query(int rt, int l, int r)121 {122 if(segTree[rt].l == l && segTree[rt].r == r)123 {124 return segTree[rt].Max;125 }126 int mid = (segTree[rt].l + segTree[rt].r) >> 1;127 if(r <= mid)128 return query(rt<<1, l, r);129 else if(l > mid)130 return query(rt<<1|1, l, r);131 else132 {133 return max(query(rt<<1, l, mid), query(rt<<1|1, mid + 1, r));134 }135 }136 137 int find(int u, int v)138 {139 int f1 = top[u], f2 = top[v];140 int tmp = 0;141 //保证u的节点编号比v小142 //且u,v跳到一条链上去143 while(f1 != f2)144 {145 if(deep[f1] < deep[f2])146 {147 swap(f1, f2);148 swap(u, v);149 }150 //跳深度深（链更低）的链顶点151 tmp = max(tmp, query(1, p[f1], p[u]));152 u = fa[f1];153 f1 = top[u];154 }155 if(u == v) return tmp;156 if(deep[u] > deep[v]) swap(u, v);157 return max(tmp, query(1, p[son[u]], p[v]));158 159 }160 161 162 int main()163 {164 //freopen("input.txt", "r", stdin);165 int T;166 scanf("%d", &T);167 while(T--)168 {169 170 init();171 char op[10];172 int u, v;173 scanf("%d", &N);174 for(int i = 0; i < N-1; i++)175 {176 scanf("%d %d %d", &e[i][0], &e[i][1], &e[i][2]);177 addedge(e[i][0], e[i][1]);178 addedge(e[i][1], e[i][0]);179 }180 dfs1(1, 0, 0);181 dfs2(1, 1);182 build(1, 0, pos - 1);183 184 for(int i = 0; i < N-1; i++)185 {186 if(deep[e[i][0]] < deep[e[i][1]])187 swap(e[i][0], e[i][1]);188 update(1, p[e[i][0]], e[i][2]);189 }190 while(scanf("%s", op) == 1)191 {192 if(op[0] == 'D')193 break;194 scanf("%d %d", &u, &v);195 if(op[0] == 'C')196 update(1, p[e[u-1][0]], v);197 else198 printf("%d\n", find(u, v));199 }200 }201 return 0;202 }