用线段树求解，这里注意因为求的是路径最大值，注意一下细节。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 10010;
#define lson (pos<<1)
#define rson (pos<<1|1)
const int INF = (1 << 30);
int n;
//--------------------------------------------------
struct Edge{
int to,next;
}edge[MAXN * 2];
int head[MAXN],tot;
int top[MAXN];
int fa[MAXN];
int deep[MAXN];
int num[MAXN];
int p[MAXN];
int fp[MAXN];
int son[MAXN];
int pos;
void init(){
tot = 0;
memset(head,-1,sizeof(head));
pos = 1;
memset(son,-1,sizeof(son));
}
void addedge(int u,int v){
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot ++;
}
void dfs1(int u,int pre,int d){
deep[u] = d;
fa[u] = pre;
num[u] = 1;
for(int i = head[u]; i != -1; i = edge[i].next){
int v = edge[i].to;
if(v != pre){
dfs1(v,u,d + 1);
num[u] += num[v];
if(son[u] == -1 || num[v] > num[son[u]])
son[u] = v; //找重儿子
}
}
}
void getpos(int u,int sp){
top[u] = sp;
p[u] = pos++;
//printf("%d %d
",u,p[u]);
fp[p[u]] = u;
if(son[u] == -1) return;
getpos(son[u],sp);
for(int i = head[u]; i != -1; i = edge[i].next){
int v = edge[i].to;
if(v != son[u] && v!= fa[u])
getpos(v,v);
}
}
//----------------------------------------------
int maxv[MAXN << 2]; //该一条边
void build(){
memset(maxv,0,sizeof(maxv));
}
void pushup(int pos){
maxv[pos] = max(maxv[lson],maxv[rson]);
}
void update(int l,int r,int to,int value,int pos){
if(l == r){
maxv[pos] = value;
return;
}
int mid = (l + r) >> 1;
if(to <= mid)
update(l,mid,to,value,lson);
else
update(mid + 1,r,to,value,rson);
pushup(pos);
}
int query(int l,int r,int L,int R,int pos){
if(L <= l && r <= R)
return maxv[pos];
int mid = (l + r) >> 1;
int ret = - INF;
if(L <= mid)
ret = max(ret,query(l,mid,L,R,lson));
if(R > mid)
ret = max(ret,query(mid + 1,r,L,R,rson));
return ret;
}
//-------------------------------------------------------
int find(int u,int v){
int f1 = top[u],f2 = top[v];
int tmp = 0;
while(f1 != f2){
if(deep[f1] < deep[f2]){
swap(f1,f2);
swap(u,v);
}
tmp = max(tmp,query(1,pos,p[f1],p[u],1));
u = fa[f1];
f1 = top[u];
}
if(u == v) return tmp;
if(deep[u] > deep[v]) swap(u,v);
return max(tmp,query(1,pos,p[son[u]],p[v],1));
}
//----------------------------------------------------------
struct E{
int from,to,value;
}e[MAXN];
int main(){
int T;
int u,v;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
init();
for(int i = 0; i < n - 1; i++){
scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].value);
addedge(e[i].from,e[i].to);
addedge(e[i].to,e[i].from);
}
dfs1(1,0,0);
getpos(1,1);
build();
for(int i = 0; i < n - 1; i++){
if(deep[e[i].from] > deep[e[i].to])
swap(e[i].from,e[i].to); //这里是更新一条线段，不是一个点
update(1,pos,p[e[i].to],e[i].value,1);
}
char op[10];
while(scanf("%s",op) != EOF){
if(op[0] == 'D') break;
scanf("%d%d",&u,&v);
if(op[0] == 'Q'){
printf("%d
",find(u,v));
}
else{
update(1,pos,p[e[u - 1].to],v,1);
}
}
if(T) puts("");
}
return 0;
}