题目链接：http://poj.org/problem?id=3237
一棵有边权的树，有3种操作。
树链剖分+线段树lazy标记。lazy为0表示没更新区间或者区间更新了2的倍数次，1表示为更新，每次更新异或1就可以。
熟悉线段树成段更新就很简单了，最初姿势不对一直wa，还是没有彻底理解lazy标记啊。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 1e4 + ;
struct EDGE {
int next , to , cost;
}edge[MAXN << ];
int head[MAXN] , tot;
int par[MAXN] , size[MAXN] , son[MAXN] , dep[MAXN];
int top[MAXN] , id[MAXN] , cnt;
int from[MAXN] , to[MAXN] , cost[MAXN]; void init() {
tot = cnt = ;
memset(head , - , sizeof(head));
} inline void add(int u , int v , int cost) {
edge[tot].next = head[u];
edge[tot].to = v;
head[u] = tot++;
} void dfs1(int u , int p , int d) {
par[u] = p , size[u] = , son[u] = u , dep[u] = d;
for(int i = head[u] ; ~i ; i = edge[i].next) {
int v = edge[i].to;
if(v == p)
continue;
dfs1(v , u , d + );
if(size[v] >= size[son[u]])
son[u] = v;
size[u] += size[v];
}
} void dfs2(int u , int p , int t) {
top[u] = t , id[u] = ++cnt;
if(son[u] != u)
dfs2(son[u] , u , t);
for(int i = head[u] ; ~i ; i = edge[i].next) {
int v = edge[i].to;
if(v == p || v == son[u])
continue;
dfs2(v , u , v);
}
} struct SegTree {
int l , r , Max , lazy , Min; //lazy变量0表示无更新 1表示有更新
}T[MAXN << ]; void build(int p , int l , int r) {
int mid = (l + r) >> ;
T[p].l = l , T[p].r = r , T[p].lazy = ;
if(l == r) {
return ;
}
build(p << , l , mid);
build((p << )| , mid + , r);
} void pushup(int p) {
if(T[p].lazy) {
int ls = p << , rs = (p << )|;
T[ls].lazy ^= ;
T[rs].lazy ^= ; int temp;
temp = T[ls].Max;
T[ls].Max = -T[ls].Min;
T[ls].Min = -temp; temp = T[rs].Max;
T[rs].Max = -T[rs].Min;
T[rs].Min = -temp;
T[p].lazy = ;
}
}
//更新操作就是 将原来的Max变成-Min ，Min变成-Max
void updata(int p , int l , int r , int flag) {
int mid = (T[p].r + T[p].l) >> ;
if(T[p].l == l && T[p].r == r) {
T[p].lazy ^= flag;
int temp = T[p].Max;
T[p].Max = -T[p].Min;
T[p].Min = -temp;
return ;
}
pushup(p);
if(r <= mid) {
updata(p << , l , r , flag);
}
else if(l > mid) {
updata((p << )| , l , r , flag);
}
else {
updata(p << , l , mid , flag);
updata((p << )| , mid + , r , flag);
}
T[p].Max = max(T[p << ].Max , T[(p << )|].Max);
T[p].Min = min(T[p << ].Min , T[(p << )|].Min);
} int query(int p , int l , int r) {
int mid = (T[p].l + T[p].r) >> ;
if(T[p].l == l && T[p].r == r) {
return T[p].Max;
}
pushup(p);
if(r <= mid) {
return query(p << , l , r);
}
else if(l > mid) {
return query((p << )| , l , r);
}
else {
return max(query(p << , l , mid) , query((p << )| , mid + , r));
}
} void updata_pos(int p , int pos , int num) {
int mid = (T[p].l + T[p].r) >> ;
if(T[p].l == T[p].r && T[p].l == pos) {
T[p].Max = T[p].Min = num;
T[p].lazy = ;
return ;
}
pushup(p);
if(pos <= mid) {
updata_pos(p << , pos , num);
}
else {
updata_pos((p << )| , pos , num);
}
T[p].Max = max(T[p << ].Max , T[(p << )|].Max);
T[p].Min = min(T[p << ].Min , T[(p << )|].Min);
} int find_max(int u , int v) {
int fu = top[u] , fv = top[v] , Max = -;
while(fv != fu) {
if(dep[fu] > dep[fv]) {
Max = max(Max , query( , id[fu] , id[u]));
u = par[fu];
fu = top[u];
}
else {
Max = max(Max , query( , id[fv] , id[v]));
v = par[fv];
fv = top[v];
}
}
if(v == u)
return Max;
else if(dep[u] > dep[v])
return max(Max , query( , id[son[v]] , id[u]));
else
return max(Max , query( , id[son[u]] , id[v]));
} void change(int u , int v) {
int fu = top[u] , fv = top[v];
while(fu != fv) {
if(dep[fu] > dep[fv]) {
updata( , id[fu] , id[u] , );
u = par[fu];
fu = top[u];
}
else {
updata( , id[fv] , id[v] , );
v = par[fv];
fv = top[v];
}
}
if(v == u)
return ;
else if(dep[u] > dep[v])
updata( , id[son[v]] , id[u] , );
else
updata( , id[son[u]] , id[v] , );
} int main()
{
int t, n;
scanf("%d", &t);
while(t--) {
init();
scanf("%d" , &n);
for(int i = ; i < n ; ++i) {
scanf("%d %d %d" , from + i , to + i , cost + i);
add(from[i] , to[i] , cost[i]);
add(to[i] , from[i] , cost[i]);
}
dfs1( , , );
dfs2( , , );
build( , , cnt);
for(int i = ; i < n ; ++i) {
if(dep[from[i]] < dep[to[i]])
swap(from[i] , to[i]);
updata_pos( , id[from[i]] , cost[i]);
}
char q[];
int l , r;
while(scanf("%s" , q) && q[] != 'D') {
scanf("%d %d" , &l , &r);
if(q[] == 'Q') {
printf("%d\n" , find_max(l , r));
}
else if(q[] == 'N') {
change(l , r);
}
else {
updata_pos( , id[from[l]] , r);
}
}
}
return ;
}