Description
一棵树上有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本身
Input
输入的第一行为一个整数n，表示节点的个数。接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有一条边相连。接下来n行，每行一个整数，第i行的整数wi表示节点i的权值。接下来1行，为一个整数q，表示操作的总数。接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。 对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。
Output
对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。
动态树的题目似乎都大同小异啊。
#include<iostream> #include<cstdio> #include<cstring> #define MAXN 30005 using namespace std; int ch[MAXN][2],fa[MAXN],sum[MAXN],maxz[MAXN],val[MAXN]; char opt[10]; bool rev[MAXN],tp[MAXN]; int n,q; struct bian { int u,v; }e[MAXN]; void getint(int &num) { num=0; char c; int flag=1; while((c=getchar())&&!isdigit(c))if(c=='-')flag=-1; while(isdigit(c)){num=num*10+c-48;c=getchar(); } num*=flag; } void pushdown(int r) { if(rev[r]) {rev[r]=0; swap(ch[r][0],ch[r][1]); if(ch[r][0])rev[ch[r][0]]^=1; if(ch[r][1])rev[ch[r][1]]^=1; } } void pushup(int r) { sum[r]=sum[ch[r][0]]+sum[ch[r][1]]+val[r]; maxz[r]=val[r]; if(ch[r][0])maxz[r]=max(maxz[ch[r][0]],maxz[r]); if(ch[r][1])maxz[r]=max(maxz[ch[r][1]],maxz[r]); } void rot(int r) {if(r==0||tp[r]==0)return; pushdown(r); int y=fa[r],z=fa[y]; bool flag=(ch[y][1]==r); ch[y][flag]=ch[r][!flag]; if(ch[y][flag])fa[ch[y][flag]]=y; ch[r][!flag]=y; fa[y]=r; fa[r]=z; if(tp[y]==1)ch[z][ch[z][1]==y]=r; tp[r]=tp[y]; rev[r]=rev[y]; rev[y]=0; tp[y]=1; pushup(y); //pushup(r); } void splay(int r) { for(;tp[r]==1;rot(r)) { int y=fa[r]; if(y&&tp[y]==1) { int z=fa[y]; rot(((ch[y][0]==r)==(ch[z][0]==y))?y:r); } } pushup(r); pushdown(r); } int access(int r) { int last=0; while(r) { splay(r); if(ch[r][1])tp[ch[r][1]]=0; ch[r][1]=last; pushup(r); if(last)tp[last]=1; last=r; r=fa[r]; } return last; } void beroot(int r) { access(r); splay(r); rev[r]^=1; pushdown(r); } void link(int u,int v) { beroot(u); fa[u]=v; } int querysum(int u,int v) { beroot(u); access(v); splay(v); return sum[v]; } int querymax(int u,int v) { beroot(u); access(v); splay(v); return maxz[v]; } int main() { getint(n); int t1,t2; for(int i=1;i<n;i++) { getint(e[i].u),getint(e[i].v); } for(int i=1;i<=n;i++) getint(val[i]); for(int i=1;i<=n;i++) { sum[i]=maxz[i]=val[i]; } for(int i=1;i<n;i++) { link(e[i].u,e[i].v); } getint(q); for(int i=1;i<=q;i++) { scanf("%s",opt); getint(t1),getint(t2); if(opt[1]=='H') { val[t1]=t2; pushup(t1); access(t1); splay(t1); } else if(opt[1]=='M') { printf("%d ",querymax(t1,t2)); } else if(opt[1]=='S') printf("%d ",querysum(t1,t2)); } return 0; }