树链剖分+线段树lazy-tag
在树链上操作时千万不要写错。。
/*
树链剖分+线段树区间变负
*/
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define maxn 10005
struct Edge{
int to,next;
}edge[maxn<<];
int head[maxn],tot,e[maxn][];
int fa[maxn],son[maxn],num[maxn],deep[maxn];
int top[maxn],fp[maxn],p[maxn],pos;
inline 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 dep){
fa[u]=pre;num[u]=;deep[u]=dep;
for(int i=head[u];i!=-;i=edge[i].next){
int v=edge[i].to;
if(v==pre) continue;
dfs1(v,u,dep+);
num[u]+=num[v];
if(son[u]==- || num[son[u]]<num[v]) son[u]=v;
}
}
void getpos(int u,int sp){
top[u]=sp;p[u]=pos++;fp[p[u]]=u;
if(son[u]==-) return;
getpos(son[u],sp);
for(int i=head[u];i!=-;i=edge[i].next){
int v=edge[i].to;
if(v!=fa[u] && v!=son[u]) getpos(v,v);
}
} #define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int Max[maxn<<],Min[maxn<<],rev[maxn<<];//遇到区间取反的通常维护一下区间两个极值
void build(int l,int r,int rt){
Max[rt]=Min[rt]=rev[rt]=;
if(l==r) return;
int m=l+r>>;
build(lson);build(rson);
}
inline void pushup(int rt){
Max[rt]=max(Max[rt<<],Max[rt<<|]);
Min[rt]=min(Min[rt<<],Min[rt<<|]);
}
inline void pushdown(int rt){
if(rev[rt]){
rev[rt<<]^=,rev[rt<<|]^=;
swap(Min[rt<<],Max[rt<<]);
Min[rt<<]*=-,Max[rt<<]*=-;
swap(Min[rt<<|],Max[rt<<|]);
Min[rt<<|]*=-,Max[rt<<|]*=-;
rev[rt]=;
}
}
void update(int pos,int val,int l,int r,int rt){
if(l==r){Max[rt]=Min[rt]=val;rev[rt]=;return;}
int m=l+r>>;
pushdown(rt);
if(pos<=m) update(pos,val,lson);
else update(pos,val,rson);
pushup(rt);
}
void seg_negate(int L,int R,int l,int r,int rt){
if(L<=l && R>=r){
swap(Min[rt],Max[rt]);
Min[rt]*=-,Max[rt]*=-;
rev[rt]^=;
return;
}
pushdown(rt);
int m=l+r>>;
if(L<=m) seg_negate(L,R,lson);
if(R>m) seg_negate(L,R,rson);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt){
if(L<=l && R>=r)return Max[rt];
pushdown(rt);
int m=l+r>>,res=-;
if(L<=m) res=max(res,query(L,R,lson));
if(R>m) res=max(res,query(L,R,rson));
pushup(rt);
return res;
}
int find(int u,int v)//查询u->v边的最大值
{
int f1 = top[u], f2 = top[v];
int tmp = -;
while(f1 != f2)
{
if(deep[f1] < deep[f2])
{
swap(f1,f2);
swap(u,v);
}
tmp = max(tmp,query(p[f1],p[u],,pos,));
u = fa[f1]; f1 = top[u];
}
if(u == v)return tmp;
if(deep[u] > deep[v]) swap(u,v);
return max(tmp,query(p[son[u]],p[v],,pos,));
}
void Negate(int u,int v)//把u-v路径上的边的值都设置为val
{
int f1 = top[u], f2 = top[v];
while(f1 != f2)
{
if(deep[f1] < deep[f2])
{
swap(f1,f2);
swap(u,v);
}
seg_negate(p[f1],p[u],,pos,);
u = fa[f1]; f1 = top[u];
}
if(u == v)return;
if(deep[u] > deep[v]) swap(u,v);
return seg_negate(p[son[u]],p[v],,pos,);
}
void init(){
tot=pos=;
memset(head,-,sizeof head);
memset(son,-,sizeof son);
}
int main(){
int T,n,a,b,c;
char op[];
cin >> T;
while(T--){
init();
scanf("%d",&n);
for(int i=;i<=n-;i++){
scanf("%d%d%d",&e[i][],&e[i][],&e[i][]);
addedge(e[i][],e[i][]);addedge(e[i][],e[i][]);
}
dfs1(,,);getpos(,);build(,pos,);
for(int i=;i<=n-;i++){
if(deep[e[i][]]>deep[e[i][]]) swap(e[i][],e[i][]);
update(p[e[i][]],e[i][],,pos,);
} while(scanf("%s",op)){
if(op[]=='D') break;
scanf("%d%d",&a,&b);
if(op[]=='C')update(p[e[a][]],b,,pos,);
else if(op[]=='N') Negate(a,b);
else printf("%d\n",find(a,b));
}
}
}