题目链接：http://poj.org/problem?id=3237
题意：给定一棵n个结点n-1条边的树。 每条边都是一个边权。 现在有4种操作
1：CHANGE I V：把(输入的)第i条边的边权改为V
2：NEGATE a b:把点a到点b的路径上的边权取反
3：QUERY a b:输出点a到点b的路径上边权最大值。
4：DONE：结束操作。
思路：树链剖分。 涉及的是边权所以把边权转化为点权，做法是将边权赋值到这条边deep大的点上。 剖分后用线段树维护。 1操作对应单点更新 2操作对应区间更新 3操作对应区间查询。
对于2操作。用线段树维护一个结点的最大值和最小值。那么反正相当于把最大值和最小值互换然后分别乘上个(-1)。
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<time.h>
#include<cmath>
#include<sstream>
#include<assert.h>
using namespace std;
#define L(x) x<<1
#define R(x) x<<1|1
typedef long long int LL;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;
const int MAXN = + ;
int val[MAXN],head[MAXN], tot, cnt, edgesId[MAXN];
struct Edge{
int to, next;
int value;
}Edges[MAXN * ];
void add(int u, int v, int w){
Edges[tot].to = v;
Edges[tot].value = w;
Edges[tot].next = head[u];
head[u] = tot++;
}
int id[MAXN], son[MAXN], deep[MAXN], size[MAXN], fa[MAXN], reid[MAXN], top[MAXN];
void Init(){
tot = ; cnt = ;
memset(head, -, sizeof(head));
memset(son, -, sizeof(son));
memset(val, , sizeof(val));
}
void DFS1(int u, int p,int dep){
fa[u] = p; size[u] = ; deep[u] = dep;
for (int i = head[u]; i != -; i = Edges[i].next){
if (Edges[i].to != p){
val[Edges[i].to] = Edges[i].value; //deep大的点获得边权
edgesId[(int)ceil(i / 2.0)] = Edges[i].to;
DFS1(Edges[i].to, u,dep+);
size[u] += size[Edges[i].to];
if (son[u] == - || size[Edges[i].to] > size[son[u]]){
son[u] = Edges[i].to;
}
}
}
}
void DFS2(int u, int tp){
id[u] = ++cnt; reid[id[u]] = u; top[u] = tp;
if (son[u] == -){ return; }
DFS2(son[u], tp);
for (int i = head[u]; i != -; i = Edges[i].next){
if (son[u] != Edges[i].to&&Edges[i].to != fa[u]){
DFS2(Edges[i].to, Edges[i].to);
}
}
}
struct Node{
int st, ed;
int lazy, Max, Min;
}Seg[MAXN * ];
void Build(int l, int r, int k){
Seg[k].st = l; Seg[k].ed = r; Seg[k].lazy = ;
if (l == r){
Seg[k].Max = Seg[k].Min = val[reid[l]];
return;
}
int mid = (l + r) / ;
Build(l, mid, L(k)); Build(mid + , r, R(k));
Seg[k].Max = max(Seg[L(k)].Max, Seg[R(k)].Max);
Seg[k].Min = min(Seg[L(k)].Min, Seg[R(k)].Min);
}
void Modify(int k){
swap(Seg[k].Min, Seg[k].Max);
Seg[k].Min *= -;
Seg[k].Max *= -;
}
void pushUp(int k){
Seg[k].Max = max(Seg[L(k)].Max, Seg[R(k)].Max);
Seg[k].Min = min(Seg[L(k)].Min, Seg[R(k)].Min);
}
void pushDown(int k){
if (Seg[k].lazy){
Seg[k].lazy ^= ;
Seg[L(k)].lazy ^= ;
Modify(L(k));
Seg[R(k)].lazy ^= ;
Modify(R(k));
}
}
void CHANGE(int pos, int val, int k){
if (Seg[k].st ==Seg[k].ed){
Seg[k].Max = Seg[k].Min = val;
return;
}
pushDown(k);
if (pos <= Seg[L(k)].ed){
CHANGE(pos, val, L(k));
}
else{
CHANGE(pos, val, R(k));
}
pushUp(k);
}
void NEGATE(int l, int r, int k){
if (Seg[k].st == l&&Seg[k].ed == r){
Seg[k].lazy ^= ;
Modify(k);
return;
}
pushDown(k);
if (r <= Seg[L(k)].ed){
NEGATE(l, r, L(k));
}
else if (l >= Seg[R(k)].st){
NEGATE(l, r, R(k));
}
else{
NEGATE(l, Seg[L(k)].ed, L(k));
NEGATE(Seg[R(k)].st, r, R(k));
}
pushUp(k);
}
void NEGATE(int u, int v){
int f1 = top[u], f2 = top[v];
while (f1 != f2){
if (deep[f1] < deep[f2]){
swap(f1, f2);
swap(u, v);
}
NEGATE(id[f1], id[u], );
u = fa[f1]; f1 = top[u];
}
if (u == v){ return; }
if (deep[u] > deep[v]){
swap(u, v);
}
NEGATE(id[son[u]], id[v], );
}
int Query(int l, int r, int k){
if (Seg[k].st == l&&Seg[k].ed == r){
return Seg[k].Max;
}
int _Max = -inf;
pushDown(k);
if (r <= Seg[L(k)].ed){
_Max = Query(l, r, L(k));
}
else if (l >= Seg[R(k)].st){
_Max = Query(l, r, R(k));
}
else{
_Max = max(Query(l, Seg[L(k)].ed, L(k)), Query(Seg[R(k)].st, r, R(k)));
}
pushUp(k);
return _Max;
}
int Query(int u, int v){
int ans = -inf;
int f1 = top[u], f2 = top[v];
while (f1 != f2){
if (deep[f1] < deep[f2]){
swap(f1, f2);
swap(u, v);
}
ans = max(ans, Query(id[f1], id[u], ));
u = fa[f1]; f1 = top[u];
}
if (u == v){ return ans; }
if (deep[u] > deep[v]){
swap(u, v);
}
ans = max(ans, Query(id[son[u]], id[v], ));
return ans;
}
int main(){
//#ifdef kirito
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
//#endif
// int start = clock();
int n,t;
scanf("%d", &t);
while (t--){
scanf("%d", &n); Init();
for (int i = ; i < n; i++){
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add(u, v, w); add(v, u, w);
}
DFS1(, , ); DFS2(, ); Build(, n, );
char ope[];
while (scanf("%s",ope)&&ope[]!='D'){
int u,v;
scanf("%d%d", &u,&v);
switch (ope[])
{
case 'Q': printf("%d\n", (u==v?:Query(u, v))); break;
case 'C': CHANGE(id[edgesId[u]], v, ); break;
default: NEGATE(u, v); break;
}
}
}
//#ifdef LOCAL_TIME
// cout << "[Finished in " << clock() - start << " ms]" << endl;
//#endif
return ;
}