题目大意：
维护一棵树，每条边有边权，支持下列操作：
1.修改某条边的边权
2.将某条路经上的边权取反
3.询问某条路经上的和
4.询问某条路经上的最大值
5.询问某条路经上的最小值
--by BZOJ;
http://www.lydsy.com/JudgeOnline/problem.php?id=2157
有关树链剖分的详解，见：树链剖分
链剖模板，代码长了点，主要是线段树部分操作太多,注意可以把边权搞到点上；
代码如下：
#include<cstdio>
#define INF 0x3fffffff
using namespace std;
struct ss{
int to,next,dis;
}x[];
int first[],num;
int size[];//子树和//
int hway[];//重边//
int rank[];//点在line_tree中的位置//
int rankl[];//边所对点在line_tree中的位置//
int dis[];//点权 //
int top[];//重链顶 //
int dep[];//深度 //
int fa[];//父亲//
int a[];//line_tree的原line序列//
int ltre[];
int max[];
int min[];
int lz[];
int n,m,L,R,X,W;
void swap(int&,int&);
void build(int ,int ,int );
void dfs_1(int );
void dfs_2(int ,int );
void up(int );
void down(int ,int ,int );
void builtre(int ,int ,int );
void work(int );
int wor_(int ,int );
void chan1(int ,int ,int );
void chan2(int ,int ,int );
int sum(int ,int ,int );
int Max(int ,int ,int );
int Min(int ,int ,int );
int main()
{
int i,j,k,l;
char s[];
scanf("%d",&n);
for(i=;i<=n-;i++)
hway[i]=i;
for(i=;i<=n-;i++){
scanf("%d%d%d",&j,&k,&l);
build(j,k,l);
build(k,j,l);
}
dep[]=;
dfs_1();
num=;
dfs_2(,);
num=;
builtre(,n,);
scanf("%d",&m);
for(i=;i<=m;i++){
scanf("%s",s);
scanf("%d%d",&L,&R);
if(s[]!='\0')s[]=s[];
if(s[]=='C')X=rankl[L],W=R;
switch (s[]){
case 'C': chan1(,n,);break;//C
case 'N': work();break;//N
case 'U': work();break;//NUM
case 'A': work();break;//MAX
case 'I': work();break;//MIN
}
}
}
void swap(int &a,int &b){
int i;
i=a;a=b;b=i;
}
void build(int f,int t,int l){
x[++num].next=first[f];
x[num].dis=l;
x[num].to=t;
first[f]=num;
}
void dfs_1(int now){
int j=first[now];
while(j){
if(!dep[x[j].to]){
dis[x[j].to]=x[j].dis;
dep[x[j].to]=dep[now]+;
fa[x[j].to]=now;
dfs_1(x[j].to);
size[now]+=size[x[j].to];
if(hway[now]==now||size[x[j].to]>size[hway[now]])
hway[now]=x[j].to;
}
j=x[j].next;
}
size[now]++;
}
void dfs_2(int now,int to_nu){
int j=first[now];
top[now]=to_nu;
rank[now]=++num;
a[num]=now;
if(hway[now]!=now)
dfs_2(hway[now],to_nu);
while(j){
if(dep[x[j].to]>dep[now]&&x[j].to!=hway[now])
rankl[(j+)>>]=num+,dfs_2(x[j].to,x[j].to);
if(x[j].to==hway[now])
rankl[(j+)>>]=rank[hway[now]];
j=x[j].next;
}
}
void up(int nu){
ltre[nu]=ltre[nu<<]+ltre[nu<<|];
max[nu]=max[nu<<]>max[nu<<|]?max[nu<<]:max[nu<<|];
min[nu]=min[nu<<]<min[nu<<|]?min[nu<<]:min[nu<<|];
}
void down(int l,int r,int nu){
if(!lz[nu]) return;
lz[nu<<]^=;lz[nu<<|]^=;
swap(max[nu<<],min[nu<<]);
max[nu<<]=-max[nu<<]; min[nu<<]=-min[nu<<];
ltre[nu<<]=-ltre[nu<<];
swap(max[nu<<|],min[nu<<|]);
max[nu<<|]=-max[nu<<|]; min[nu<<|]=-min[nu<<|];
ltre[nu<<|]=-ltre[nu<<|];
lz[nu]=;
}
void builtre(int l,int r,int nu){
if(l==r){
max[nu]=min[nu]=ltre[nu]=dis[a[++num]];
if(a[num]==){
max[nu]=-INF;
min[nu]=INF;
}
return;
}
int mid=(l+r)>>;
builtre(l,mid,nu<<);
builtre(mid+,r,nu<<|);
up(nu);
}
void work(int x){
int ans=;
if(x==)ans=-INF;
if(x==)ans=INF;
int u=L,v=R;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])
L=rank[top[v]],R=rank[v],v=fa[top[v]];
else
L=rank[top[u]],R=rank[u],u=fa[top[u]];
ans=wor_(ans,x);
}
if(u!=v){
if(dep[u]>dep[v])
swap(u,v);
u=hway[u];
L=rank[u];R=rank[v];
ans=wor_(ans,x);
}
if(x>=)
printf("%d\n",ans);
}
int wor_(int ans,int x){
int i;
if(x==)
chan2(,n,);
if(x==)
ans+=sum(,n,);
if(x==){
i=Max(,n,);ans=ans>i?ans:i;}
if(x==){
i=Min(,n,);ans=ans<i?ans:i;}
return ans;
}
void chan1(int l,int r,int nu){
if(l==r){
max[nu]=min[nu]=ltre[nu]=W ;
return;
}
int mid=(l+r)>>;
down(l,r,nu);
if(X<=mid)
chan1(l,mid,nu<<);
if(X>mid)
chan1(mid+,r,nu<<|);
up(nu);
}
void chan2(int l,int r,int nu){
if(L<=l&&r<=R){
swap(max[nu],min[nu]);
max[nu]=-max[nu];
min[nu]=-min[nu];
ltre[nu]=-ltre[nu];
lz[nu]^=;
return ;
}
down(l,r,nu);
int mid=(l+r)>>;
if(L<=mid)
chan2(l,mid,nu<<);
if(R>mid)
chan2(mid+,r,nu<<|);
up(nu);
}
int sum(int l,int r,int nu){
if(L<=l&&r<=R)
return ltre[nu];
down(l,r,nu);
int mid=(l+r)>>,re=;
if(L<=mid)
re+=sum(l,mid,nu<<);
if(R>mid)
re+=sum(mid+,r,nu<<|);
return re;
}
int Max(int l,int r,int nu){
if(L<=l&&r<=R)
return max[nu];
down(l,r,nu);
int mid=(l+r)>>,lm=-INF,rm=-INF;
if(L<=mid)
lm=Max(l,mid,nu<<);
if(R>mid)
rm=Max(mid+,r,nu<<|);
if(lm>=rm)
return lm;
return rm;
}
int Min(int l,int r,int nu){
if(L<=l&&r<=R)
return min[nu];
down(l,r,nu);
int mid=(l+r)>>,lm=INF,rm=INF;
if(L<=mid)
lm=Min(l,mid,nu<<);
if(R>mid)
rm=Min(mid+,r,nu<<|);
if(lm<=rm)
return lm;
return rm;
}
祝AC哟；