题目链接：http://poj.org/problem?id=3237
You are given a tree with N nodes. The tree’s nodes are numbered 1 through N and its edges are numbered 1 through N − 1. Each edge is associated with a weight. Then you are to execute a series of instructions on the tree. The instructions can be one of the following forms:
CHANGE i v
|
Change the weight of the ith edge to v |
NEGATE a b
|
Negate the weight of every edge on the path from a to b |
QUERY a b
|
Find the maximum weight of edges on the path from a to b |
题意描述：一棵树有n个节点和n-1条边，每条边有一个权值。现在给出三种操作：
CHANGE I V：把第i条边的值改为v
NEGATE A B：把A到B的路径上的所有边的值取反（正为负，负改为正）
QUERY A B：询问A到B的路径上的边权值的最大值。
算法分析：树链剖分解决。把边权值移到节点上面，由于操作上有对值取反，所有我们不止要运用线段树统计区间最大值maxnum，还要统计区间最小值minnum，这样在取反操作后，maxnum=-maxnum，minnum=-minnum，再把两个值交换：swap（maxnum,minnum）即可。
说明：阅读了一些大牛的代码，感觉线段树部分还是结构体比数组方便一些，树链剖分刚开始学，代码和解题思想很多是借鉴大牛们的，只是把代码风格改成自己的了，相信只有不断学习和解题才会对树链剖分有一定理解的。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#define inf 0x7fffffff
using namespace std;
const int maxn=+; struct Edge
{
int to,next;
}edge[maxn*];
int head[maxn],edgenum;
int top[maxn];//top[v]表示v所在的重链的顶端节点
int fa[maxn]; //父亲节点
int dep[maxn];//深度
int siz[maxn];//siz[v]表示以v为根的子树的节点数
int tid[maxn];//tid[v]表示v与其父亲节点的连边在线段树中的位置
int tid2[maxn];//和tid数组相反
int son[maxn];//重儿子
int pos;
void init()
{
edgenum=;
memset(head,-,sizeof(head));
pos=;
memset(son,-,sizeof(son));
}
void addedge(int u,int v)
{
edge[edgenum].to=v ;edge[edgenum].next=head[u];
head[u]=edgenum++; edge[edgenum].to=u ;edge[edgenum].next=head[v];
head[v]=edgenum++;
} void dfs1(int u,int pre,int d) //第一遍dfs求出fa,dep,siz,son
{
dep[u]=d;
fa[u]=pre;
siz[u]=;
for (int i=head[u] ;i != - ;i=edge[i].next)
{
int v=edge[i].to;
if (v != pre)
{
dfs1(v,u,d+);
siz[u] += siz[v];
if (son[u] == - || siz[v]>siz[son[u]])
son[u]=v;
}
}
}
void dfs2(int u,int tp) //第二遍dfs求出top和tid
{
top[u]=tp;
tid[u]= ++pos;
tid2[pos]=u;
if (son[u] == -) return;
dfs2(son[u],tp);
for (int i=head[u] ;i != - ;i=edge[i].next)
{
int v=edge[i].to;
if (v != son[u] && v != fa[u])
dfs2(v,v);
}
} //线段树
struct node
{
int l,r;
int Max;
int Min;
int ne;
}segTree[maxn*]; void build(int l,int r,int rt)
{
segTree[rt].l=l;
segTree[rt].r=r;
segTree[rt].Max=;
segTree[rt].Min=;
segTree[rt].ne=;
if (l==r) return ;
int mid=(l+r)/;
build(l,mid,rt<<);
build(mid+,r,rt<<|);
}
void PushUP(int rt)
{
segTree[rt].Max = max(segTree[rt<<].Max,segTree[rt<<|].Max);
segTree[rt].Min = min(segTree[rt<<].Min,segTree[rt<<|].Min);
}
void PushDown(int rt)
{
if (segTree[rt].l == segTree[rt].r) return ;
if (segTree[rt].ne)
{
segTree[rt<<].Max = -segTree[rt<<].Max;
segTree[rt<<].Min = -segTree[rt<<].Min;
swap(segTree[rt<<].Min,segTree[rt<<].Max);
segTree[rt<<|].Max = -segTree[rt<<|].Max;
segTree[rt<<|].Min = -segTree[rt<<|].Min;
swap(segTree[rt<<|].Max,segTree[rt<<|].Min);
segTree[rt<<].ne ^= ;
segTree[rt<<|].ne ^= ;
segTree[rt].ne = ;
}
} void update(int k,int val,int rt) // 更新线段树的第k个值为val
{
if(segTree[rt].l == k && segTree[rt].r == k)
{
segTree[rt].Max = val;
segTree[rt].Min = val;
segTree[rt].ne = ;
return;
}
PushDown(rt);
int mid = (segTree[rt].l + segTree[rt].r)/;
if(k <= mid)update(k,val,rt<<);
else update(k,val,(rt<<)|);
PushUP(rt);
}
void ne_update(int l,int r,int rt) // 更新线段树的区间[l,r]取反
{
if (segTree[rt].l == l && segTree[rt].r == r)
{
segTree[rt].Max = -segTree[rt].Max;
segTree[rt].Min = -segTree[rt].Min;
swap(segTree[rt].Max,segTree[rt].Min);
segTree[rt].ne ^= ;
return;
}
PushDown(rt);
int mid = (segTree[rt].l + segTree[rt].r)/;
if (r <= mid) ne_update(l,r,rt<<);
else if (l > mid) ne_update(l,r,(rt<<)|);
else
{
ne_update(l,mid,rt<<);
ne_update(mid+,r,(rt<<)|);
}
PushUP(rt);
}
int query(int l,int r,int rt) //查询线段树中[l,r] 的最大值
{
if (segTree[rt].l == l && segTree[rt].r == r)
return segTree[rt].Max;
PushDown(rt);
int mid = (segTree[rt].l+segTree[rt].r)>>;
if (r <= mid) return query(l,r,rt<<);
else if (l > mid) return query(l,r,(rt<<)|);
else return max(query(l,mid,rt<<),query(mid+,r,(rt<<)|));
PushUP(rt);
}
int findmax(int u,int v)//查询u->v边的最大值
{
int f1 = top[u], f2 = top[v];
int tmp = -;
while(f1 != f2)
{
if(dep[f1] < dep[f2])
{
swap(f1,f2);
swap(u,v);
}
tmp = max(tmp,query(tid[f1],tid[u],));
u = fa[f1]; f1 = top[u];
}
if(u == v)return tmp;
if(dep[u] > dep[v]) swap(u,v);
return max(tmp,query(tid[son[u]],tid[v],));
} void Negate(int u,int v)
{
int f1=top[u],f2=top[v];
while (f1 != f2)
{
if (dep[f1]<dep[f2])
{
swap(f1,f2);
swap(u,v);
}
ne_update(tid[f1],tid[u],);
u=fa[f1] ;f1=top[u];
}
if (u==v) return;
if (dep[u]>dep[v]) swap(u,v);
return ne_update(tid[son[u] ],tid[v],);
} int e[maxn][];
int main()
{
int T;
int n;
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][]);
}
dfs1(,,);
dfs2(,);
build(,n,);
for (int i = ;i < n-; i++)
{
if (dep[e[i][]]>dep[e[i][]])
swap(e[i][],e[i][]);
update(tid[e[i][]],e[i][],);
}
char op[];
int u,v;
while (scanf("%s",op) == )
{
if (op[] == 'D') break;
scanf("%d%d",&u,&v);
if (op[]=='Q')
printf("%d\n",findmax(u,v));//查询u->v路径上边权的最大值
else if (op[]=='C')
update(tid[e[u-][]],v,);//改变第u条边的值为v
else Negate(u,v);
}
}
return ;
}