题目链接：http://poj.org/problem?id=3237
题目大意：指定一颗树上有3个操作：
1）询问操作,询问a点和b点之间的路径上最长的那条边的长度（即最大值）；
2）取反操作，将a点和b点之间的路径权值都取相反数；
3）变化操作，把某条边的权值变成指定的值。
分析：树链剖分，线段树维护好区间的最大最小值，方便取反操作更新。。。
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 10007
#define inf 0x3f3f3f3f
#define N 100010
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
struct edge
{
int to,next;
edge(){}
edge(int to,int next):to(to),next(next){}
}e[N<<];
int head[N<<],tot;
int top[N];//top[v]表示v所在的重链的顶端节点
int fa[N];//父亲节点
int dep[N];//深度
int sz[N];//si[v]表示以v为根节点的子树的节点数
int son[N];//重儿子
int p[N];//p[v]表示v与其父亲节点的连边在线段树中的位置
int fp[N];//与p数组相反
int pos;//所有链构成的线段树总长度
int mx[N<<],mn[N<<],col[N<<],E[N][];
void addedge(int u,int v)
{
e[tot]=edge(v,head[u]);
head[u]=tot++;
}
void init()
{
tot=;FILL(head,-);
pos=;FILL(son,-);
}
void dfs(int u,int f,int d)
{
dep[u]=d;sz[u]=;fa[u]=f;
for(int i=head[u];~i;i=e[i].next)
{
int v=e[i].to;
if(v==f)continue;
dfs(v,u,d+);
sz[u]+=sz[v];
if(son[u]==-||sz[son[u]]<sz[v])son[u]=v;
}
}
void getpos(int u,int sp)
{
top[u]=sp;
p[u]=++pos;
fp[pos]=u;
if(son[u]==-)return;
getpos(son[u],sp);
for(int i=head[u];~i;i=e[i].next)
{
int v=e[i].to;
if(v!=son[u]&&v!=fa[u])
{
getpos(v,v);
}
}
}
void Pushup(int rt)
{
int ls=rt<<,rs=ls|;
mx[rt]=max(mx[ls],mx[rs]);
mn[rt]=min(mn[ls],mn[rs]);
}
void Pushdown(int rt)
{
int ls=rt<<,rs=ls|;
if(col[rt])
{
mx[ls]=-mx[ls];
mn[ls]=-mn[ls];
swap(mx[ls],mn[ls]);
mx[rs]=-mx[rs];
mn[rs]=-mn[rs];
swap(mx[rs],mn[rs]);
col[ls]^=;col[rs]^=;
col[rt]=;
}
}
void update(int L,int R,int c,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
if(c!=inf)
{
mx[rt]=mn[rt]=c;
col[rt]=;
}
else
{
col[rt]^=;
mx[rt]=-mx[rt];
mn[rt]=-mn[rt];
swap(mn[rt],mx[rt]);
}
return;
}
Pushdown(rt);
int m=(l+r)>>;
if(L<=m)update(L,R,c,lson);
if(m<R)update(L,R,c,rson);
Pushup(rt);
}
int query(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
return mx[rt];
Pushdown(rt);
int m=(l+r)>>;
int res=-inf;
if(L<=m)res=max(res,query(L,R,lson));
if(m<R)res=max(res,query(L,R,rson));
return res;
}
int lca(int u,int v,int flag)
{
int fu=top[u],fv=top[v];
int res=-inf;
while(fu!=fv)
{
if(dep[fu]<dep[fv])
{
swap(fu,fv);
swap(u,v);
}
if(flag)res=max(res,query(p[fu],p[u],,pos,));
else update(p[fu],p[u],inf,,pos,);
u=fa[fu];fu=top[u];
}
if(dep[u]>dep[v])swap(u,v);
if(u!=v)
{
if(flag)res=max(res,query(p[son[u]],p[v],,pos,));
else update(p[son[u]],p[v],inf,,pos,);
}
return res;
}
int main()
{
int T,n,u,v;
scanf("%d",&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][]);
}
dfs(,,);
getpos(,);
for(int i=;i<n;i++)
{
if(dep[E[i][]]>dep[E[i][]])
swap(E[i][],E[i][]);
update(p[E[i][]],p[E[i][]],E[i][],,pos,);
}
char op[];
while()
{
scanf("%s",op);
if(op[]=='D')break;
scanf("%d%d",&u,&v);
if(op[]=='Q')
printf("%d\n",lca(u,v,));
else if(op[]=='N')lca(u,v,);
else update(p[E[u][]],p[E[u][]],v,,pos,);
}
}
}