https://www.cnblogs.com/violet-acmer/p/9711441.html
题解：
树链剖分的模板题，看代码比看文字解析理解来的快~~~~~~~
AC代码献上：
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 using namespace std; 6 #define ls(x) ((x)<<1) 7 #define rs(x) ((x)<<1 | 1) 8 const int maxn=10010; 9 10 //===========链式前向星=============== 11 struct Node1 12 { 13 int to; 14 int next; 15 }edge[2*maxn]; 16 int head[maxn]; 17 int cnt; 18 void addEdge(int u,int v) 19 { 20 edge[cnt].to=v; 21 edge[cnt].next=head[u]; 22 head[u]=cnt++; 23 } 24 //==================================== 25 //=========树链剖分用到的变量========= 26 int fa[maxn];//fa[u] : 节点u的父节点 27 int newId[maxn];//newId[u] : u与其父亲节点的连边在线段树中的位置 28 int depth[maxn];//depth[u] : 节点u的深度 29 int siz[maxn];//siz[u] : 以u为根的子树的节点数 30 int top[maxn];//top[u] : 节点u所在的重链的顶端节点 31 int son[maxn];//son[u] : 节点u重儿子 32 int label;//记录newId[]中新边对应的编号 33 //==================================== 34 //==========两次DFS()================ 35 void dfs1(int u,int f,int d) //第一遍dfs求出fa[],depth[],siz[],son[] 36 { 37 depth[u]=d; 38 fa[u]=f; 39 siz[u]=1; 40 for(int i=head[u];~i;i=edge[i].next) 41 { 42 int to=edge[i].to; 43 if(to != f) 44 { 45 dfs1(to,u,d+1); 46 siz[u] += siz[to]; 47 if(son[u] == -1 || siz[to] > siz[son[u]]) 48 son[u] = to; 49 } 50 } 51 } 52 void dfs2(int u,int sp) //第二遍dfs求出top[]和newId[] 53 { 54 top[u]=sp; 55 newId[u]=++label; 56 if(son[u] == -1) 57 return ; 58 dfs2(son[u],sp); 59 60 for(int i=head[u];~i;i=edge[i].next) 61 { 62 int to=edge[i].to; 63 if(to != son[u] && to != fa[u]) 64 dfs2(to,to); 65 } 66 } 67 //=================================== 68 //=============线段树================ 69 struct Node2 70 { 71 int l,r; 72 int Max; 73 int mid() 74 { 75 return l+((r-l)>>1); 76 } 77 }segTree[maxn*4]; 78 void buildTree(int l,int r,int pos) 79 { 80 segTree[pos].l = l,segTree[pos].r = r; 81 segTree[pos].Max = 0; 82 if(l == r) 83 return; 84 85 int mid = (l+r)/2; 86 buildTree(l,mid,ls(pos)); 87 buildTree(mid+1,r,rs(pos)); 88 } 89 void push_up(int k)//向上更新 90 { 91 segTree[k].Max = max(segTree[ls(k)].Max,segTree[rs(k)].Max); 92 } 93 void update(int k,int val,int pos) //单点更新 94 { 95 if(segTree[pos].l == segTree[pos].r) 96 { 97 segTree[pos].Max = val; 98 return; 99 } 100 101 int mid=segTree[pos].mid(); 102 103 if(k <= mid) 104 update(k,val,ls(pos)); 105 else 106 update(k,val,rs(pos)); 107 push_up(pos); 108 } 109 int query(int l,int r,int pos)//查询线段树中[l,r]的最大值 110 { 111 if(segTree[pos].l == l && segTree[pos].r == r) 112 return segTree[pos].Max; 113 114 int mid=segTree[pos].mid(); 115 116 if(r <= mid) 117 return query(l,r,ls(pos)); 118 else if(l > mid) 119 return query(l,r,rs(pos)); 120 else 121 return max(query(l,mid,ls(pos)),query(mid+1,r,rs(pos))); 122 } 123 int Find(int u,int v)//查询u->v边的最大值 124 { 125 int res=0; 126 while(top[u] != top[v]) 127 { 128 if(depth[top[u]] > depth[top[v]]) 129 { 130 res=max(res,query(newId[top[u]],newId[u],1)); 131 u=fa[top[u]]; 132 } 133 else 134 { 135 res=max(res,query(newId[top[v]],newId[v],1)); 136 v=fa[top[v]]; 137 } 138 } 139 if(u == v) 140 return res; 141 if(depth[u] > depth[v]) 142 swap(u,v); 143 return max(res,query(newId[son[u]],newId[v],1)); 144 } 145 //=================================== 146 void Init() 147 { 148 cnt=0; 149 memset(head,-1,sizeof(head)); 150 label=0; 151 memset(son,-1,sizeof(son)); 152 } 153 int e[maxn][3]; 154 int main() 155 { 156 int T; 157 scanf("%d",&T); 158 while(T--) 159 { 160 int n; 161 Init(); 162 scanf("%d",&n); 163 for(int i=1;i < n;++i) 164 { 165 scanf("%d%d%d",&e[i][0],&e[i][1],&e[i][2]); 166 addEdge(e[i][0],e[i][1]); 167 addEdge(e[i][1],e[i][0]); 168 } 169 dfs1(1,0,0); 170 dfs2(1,1); 171 buildTree(1,label,1); 172 for(int i=1;i < n;++i) 173 { 174 if(depth[e[i][0]] > depth[e[i][1]]) 175 swap(e[i][0],e[i][1]);//确保 e[i][0] 为 e[i][1]的父节点 176 update(newId[e[i][1]],e[i][2],1);//更新e[i][1]与其父节点e[i][0]的连边在线段树中的位置 177 } 178 char op[10]; 179 while(scanf("%s",op) && op[0] != 'D') 180 { 181 int u,v; 182 scanf("%d%d",&u,&v); 183 if(op[0] == 'Q') 184 printf("%d\n",Find(u,v)); 185 else 186 update(newId[e[u][1]],v,1); 187 } 188 } 189 }