题意：给一棵树，每次更新某条边或者查询u->v路径上的边权最大值。
解法：做过上一题，这题就没太大问题了，以终点的标号作为边的标号，因为dfs只能给点分配位置，而一棵树每条树边的终点只有一个。
询问的时候，在从u找到v的过程中顺便查询到此为止的最大值即可。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 10007 int siz[N]; //子树大小
int son[N]; //重儿子
int dep[N]; //深度
int pos[N]; //在线段树中的位置
int Top[N]; //所在重链的祖先
int fa[N]; //父节点
int ans[N]; //答案
int head[*N],tot,POS,n,m;
struct Edge
{
int v,next;
}G[*N];
int tree[*N];
struct node
{
int u,v,w;
}edge[N]; void init()
{
POS = tot = ;
memset(head,-,sizeof(head));
memset(son,-,sizeof(son));
memset(tree,,sizeof(tree));
} void addedge(int u,int v)
{
G[tot].v = v, G[tot].next = head[u], head[u] = tot++;
G[tot].v = u, G[tot].next = head[v], head[v] = tot++;
} void pushup(int rt)
{
tree[rt] = max(tree[*rt],tree[*rt+]);
} void update(int l,int r,int pos,int val,int rt)
{
if(l == r)
{
tree[rt] = val;
return;
}
int mid = (l+r)/;
if(pos <= mid)
update(l,mid,pos,val,*rt);
else
update(mid+,r,pos,val,*rt+);
pushup(rt);
} int query(int l,int r,int aa,int bb,int rt)
{
if(aa <= l && bb >= r)
return tree[rt];
int mid = (l+r)/;
if(bb <= mid) return query(l,mid,aa,bb,*rt);
else if(aa > mid) return query(mid+,r,aa,bb,*rt+);
return max(query(l,mid,aa,bb,*rt),query(mid+,r,aa,bb,*rt+));
} void dfs(int u,int f)
{
dep[u] = dep[f]+;
siz[u] = ;
for(int i=head[u];i!=-;i=G[i].next)
{
int v = G[i].v;
if(v == f) continue;
fa[v] = u;
dfs(v,u);
if(son[u] == - || siz[v] > siz[son[u]]) son[u] = v;
siz[u] += siz[v];
}
} void dfs2(int u,int father)
{
pos[u] = ++POS;
Top[u] = father;
if(son[u] != -) dfs2(son[u],father);
for(int i=head[u];i!=-;i=G[i].next)
{
int v = G[i].v;
if(v != fa[u] && v != son[u])
dfs2(v,v);
}
} int ask(int u,int v)
{
int fx = Top[u], fy = Top[v], maxi = ;
while(fx != fy)
{
if(dep[fx] < dep[fy])
{
swap(u,v);
swap(fx,fy);
}
maxi = max(maxi,query(,POS,pos[fx],pos[u],));
u = fa[fx];
fx = Top[u];
}
if(u == v) return maxi;
if(dep[u] > dep[v]) swap(u,v);
return max(maxi,query(,POS,pos[son[u]],pos[v],));
} int main()
{
int u,v,w,x,y,i,t;
char ss[];
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
init();
for(i=;i<n;i++)
{
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
addedge(edge[i].u,edge[i].v);
}
dep[] = ;
dfs(,);
dfs2(,);
for(i=;i<n;i++)
{
if(dep[edge[i].u] > dep[edge[i].v])
swap(edge[i].u,edge[i].v);
update(,POS,pos[edge[i].v],edge[i].w,);
}
while(scanf("%s",ss)!=EOF && ss[] != 'D')
{
if(ss[] == 'Q')
{
scanf("%d%d",&u,&v);
printf("%d\n",ask(u,v));
}
else
{
scanf("%d%d",&x,&y);
update(,POS,pos[edge[x].v],y,);
}
}
if(t >= )
puts("");
}
return ;
}