题目：
题目背景
ZJOI2008 DAY1 T4
题目描述
一棵树上有 n 个节点，编号分别为 1 到 n ，每个节点都有一个权值 w 。
我们将以下面的形式来要求你对这棵树完成一些操作：
I.CHANGE u t ：把结点 u 的权值改为 t ；
II.QMAX u v ：询问从点 u 到点 v 的路径上的节点的最大权值；
III.QSUM u v ：询问从点 u 到点 v 的路径上的节点的权值和。
注意：从点 u 到点 v 的路径上的节点包括 u 和 v 本身。
输入格式
输入第一行为一个整数 n ，表示节点的个数。
接下来 n–1 行，每行 2 个整数 a 和 b ，表示节点 a 和节点 b 之间有一条边相连。
接下来 n 行，每行一个整数，第 i 行的整数 wi 表示节点 i 的权值。
接下来 1 行，为一个整数 q ，表示操作的总数。
接下来 q 行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。
输出格式
对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。
样例数据 1
输入 []
输出
备注
【数据范围】
对于 100％ 的数据，保证1<=n<=30000；0<=q<=200000；中途操作中保证每个节点的权值 w 在 -30000 到 30000 之间。
方法：
树链剖分模板题；
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int N=3e4+;
const int inf=1e+;
int n,Q;
int first[N],next[N*],go[N*];
int size[N],top[N],father[N],pos[N],idx[N],deep[N],tot,son[N],val[N];
int summ[N*],maxx[N*];
char st[]; inline void combin(int u,int v)
{
next[++tot]=first[u],first[u]=tot,go[tot]=v;
next[++tot]=first[v],first[v]=tot,go[tot]=u;
} inline void dfs1(int u)
{
size[u]=;
for(int e=first[u],v;e;e=next[e])
{
if((v=go[e])==father[u]) continue;
father[v]=u;
deep[v]=deep[u]+;
dfs1(v);
size[u]+=size[v];
if(size[v]>size[son[u]]) son[u]=v;
}
} inline void dfs2(int u)
{
if(son[u])
{
idx[pos[son[u]]=++tot]=son[u];
top[son[u]]=top[u];
dfs2(son[u]);
}
for(int e=first[u],v;e;e=next[e])
{
if((v=go[e])==father[u]||v==son[u]) continue;
idx[pos[v]=++tot]=v;
top[v]=v;
dfs2(v);
}
} inline void pre()
{
dfs1();
top[]=pos[]=idx[]=tot=;
dfs2();
} inline void build(int k,int l,int r)
{
if(l==r)
{
summ[k]=maxx[k]=val[idx[l]];
return;
}
int mid=(l+r)/;
build(k*,l,mid);
build(k*+,mid+,r);
summ[k]=summ[k*]+summ[k*+];
maxx[k]=max(maxx[k*],maxx[k*+]);
} inline void modify(int k,int l,int r,int p,int v)
{
if(l==r)
{
summ[k]=maxx[k]=v;
return;
}
int mid=(l+r)/;
if(p<=mid) modify(k*,l,mid,p,v);
else modify(k*+,mid+,r,p,v);
summ[k]=summ[k*]+summ[k*+];
maxx[k]=max(maxx[k*],maxx[k*+]);
} inline int querymax(int k,int l,int r,int x,int y)
{
if(l>=x&&r<=y)
return maxx[k];
int mid=(l+r)/,res=-inf;
if(x<=mid) res=querymax(k*,l,mid,x,y);
if(y>mid) res=max(res,querymax(k*+,mid+,r,x,y));
return res;
} inline int querysum(int k,int l,int r,int x,int y)
{
if(l>=x&&r<=y)
return summ[k];
int mid=(l+r)/,res=;
if(x<=mid) res+=querysum(k*,l,mid,x,y);
if(y>mid) res+=querysum(k*+,mid+,r,x,y);
return res;
} inline int pathmax(int u,int v)
{
if(top[u]!=top[v])
{
if(deep[top[u]]<deep[top[v]]) swap(u,v);
return max(pathmax(father[top[u]],v),querymax(,,n,pos[top[u]],pos[u]));
}
if(deep[u]>deep[v]) swap(u,v);
return querymax(,,n,pos[u],pos[v]);
} inline int pathsum(int u,int v)
{
if(top[u]!=top[v])
{
if(deep[top[u]]<deep[top[v]]) swap(u,v);
return pathsum(father[top[u]],v)+querysum(,,n,pos[top[u]],pos[u]);
}
if(deep[u]>deep[v]) swap(u,v);
return querysum(,,n,pos[u],pos[v]);
} int main()
{
//freopen("a.in","r",stdin);
//freopen("a.out","w",stdout);
scanf("%d",&n);
int u,v;
for(int i=;i<n;i++)
{
scanf("%d%d",&u,&v);
combin(u,v);
}
for(int i=;i<=n;i++)
scanf("%d",&val[i]);
pre();
build(,,n);
scanf("%d",&Q);
while(Q--)
{
scanf("%s%d%d",st,&u,&v);
if(st[]=='M')
printf("%d\n",pathmax(u,v));
if(st[]=='S')
printf("%d\n",pathsum(u,v));
if(st[]=='H')
modify(,,n,pos[u],v);
}
return ;
}