【题意说明】
指定一棵树上有3个操作：
(1) 查询a点和b点之间的路径上最长的那条边的长度；
(2) 区域取反，将a点和b点之间的路径权值都取相反数；
(3) 单点更新，把某条边的权值变成指定的值。
【问题分析】
显然对树上进行区域操作，可以用树链剖分来解决。由于有取反操作，所以在线段树的结点上记录区域的最大值和最小值，取反操作时只需要把最小值取反给最大值，最大值取反给最小值。注意取反运算延迟标记的使用（两次取反等于未操作）。
【参考代码】
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define lson k<<1
#define rson k<<1|1
#define lt(i) tree[i].left
#define rt(i) tree[i].right
#define mx(i) tree[i].max
#define mn(i) tree[i].min
#define ct(i) tree[i].cnt
#define fr(i) edge[i].from
#define to(i) edge[i].to
#define nx(i) edge[i].next
#define vl(i) edge[i].value
#define dp(i) node[i].deep
#define tp(i) node[i].top
#define fa(i) node[i].father
#define hd(i) node[i].head
#define sz(i) node[i].size
#define sn(i) node[i].son
#define id(i) node[i].id
const int maxN=10010;
const int INF=1000000000;
struct Tree{
int left, right, max, min, cnt;
}tree[maxN<<2];
struct Node{
int top, head, father, deep, size, son, id;
}node[maxN];
struct Edge{
int from, to, next, value;
}edge[maxN<<1];
int n, total;
void init();
void work();
void addedge(int, int, int, int);
void dfs1(int, int);
void dfs2(int, int);
void build(int, int, int);
void update(int, int, int, int);
void pushdown(int);
void pushup(int);
void update(int, int, int, int, int);
void change1(int, int);
void change2(int, int);
int query(int, int, int);
void refresh(int, int, int);
int solve(int, int);
int main(){
freopen("poj3237.in", "r", stdin);
freopen("poj3237.out", "w", stdout);
int t; scanf("%d", &t);
while(t--) {init(); work();}
fclose(stdin);
fclose(stdout);
return 0;
}
void init(){
memset(tree, 0, sizeof(tree));
memset(node, 0, sizeof(node));
memset(edge, 0, sizeof(edge));
total=0;
scanf("%d", &n);
for(int i=1; i<n; i++){
int x, y, c;
scanf("%d%d%d", &x, &y, &c);
addedge(x, y, c, i);
addedge(y, x, c, i+n);
}
dfs1(1, 1);
dfs2(1, 1);
}
void addedge(int x, int y, int c, int k){
fr(k)=x; to(k)=y; vl(k)=c;
nx(k)=hd(x); hd(x)=k;
}
void dfs1(int k, int _dp){
sz(k)=1; dp(k)=_dp;
for(int i=hd(k); i; i=nx(i)){
if(sz(to(i))) continue;
fa(to(i))=k;
dfs1(to(i), _dp+1);
sz(k)+=sz(to(i));
if(sz(sn(k))<sz(to(i))) sn(k)=to(i);
}
}
void dfs2(int k, int _tp){
id(k)=++total; tp(k)=_tp;
if(sn(k)) dfs2(sn(k), _tp);
for(int i=hd(k); i; i=nx(i))
if(!id(to(i))) dfs2(to(i), to(i));
}
void work(){
build(1, 1, n);
for(int i=1; i<n; i++) change1(i, vl(i));
char ch[10]; int x, y;
scanf("%s", ch);
while(ch[0]!='D'){
scanf("%d%d", &x, &y);
if(ch[0]=='Q')
printf("%d ", solve(x, y));
else if(ch[0]=='C') change1(x, y);
else change2(x, y);
scanf("%s", ch);
}
}
void build(int k, int l, int r){
lt(k)=l; rt(k)=r; mx(k)=-INF; mn(k)=INF;
if(l==r) return;
int mid=(l+r)>>1;
build(lson, l, mid);
if(mid<r) build(rson, mid+1, r);
}
void change1(int k, int w){
int u=fr(k), v=to(k);
if(dp(u)<dp(v)) swap(u, v);
update(1, id(u), id(u), 1, w);
}
void change2(int u, int v){
int f1=tp(u), f2=tp(v);
while(f1!=f2){
if(dp(f1)<dp(f2)){
swap(u, v);
swap(f1, f2);
}
update(1, id(f1), id(u), -1, 0);
u=fa(f1); f1=tp(u);
}
if(u==v) return;
if(dp(u)<dp(v)) swap(u, v);
update(1, id(sn(v)), id(u), -1, 0);
}
void update(int k, int l, int r, int flag, int w){
if(l<=lt(k)&&r>=rt(k)){
refresh(k, flag, w);
return;
}
pushdown(k);
if(l<=rt(lson)) update(lson, l, r, flag, w);
if(r>=lt(rson)) update(rson, l, r, flag, w);
pushup(k);
}
void refresh(int k, int flag, int w){
if(flag<0){
int t=-mx(k); mx(k)=-mn(k); mn(k)=t;
if(!ct(k)) ct(k)=-1; else ct(k)=0;
}else {mx(k)=mn(k)=w; ct(k)=0;}
}
void pushdown(int k){
if(ct(k)){
refresh(lson, ct(k), mx(k));
refresh(rson, ct(k), mx(k));
ct(k)=0;
}
}
void pushup(int k){
mx(k)=max(mx(lson), mx(rson));
mn(k)=min(mn(lson), mn(rson));
}
int solve(int u, int v){
int f1=tp(u), f2=tp(v), ans=-100000;
while(f1!=f2){
if(dp(f1)<dp(f2)) {
swap(u, v);
swap(f1, f2);
}
ans=max(ans, query(1, id(f1), id(u)));
u=fa(f1); f1=tp(u);
}
if(u==v) return ans;
if(dp(u)<dp(v)) swap(u, v);
return max(ans, query(1, id(sn(v)), id(u)));
}
int query(int k, int l, int r){
if(l<=lt(k)&&r>=rt(k)) return mx(k);
pushdown(k);
int ans=-100000;
if(l<=rt(lson)) ans=max(ans, query(lson, l, r));
if(r>=lt(rson)) ans=max(query(rson, l, r), ans);
return ans;
}