经验值：3200
时间限制：1000毫秒
内存限制：512MB
题目描述 Description
一树上有 nn 个节点，编号分别为 11 到 nn，每个节点都有一个权值 ww。我们将以下面的形式来要求你对这棵树完成一些操作：
CHANGE u t：把节点 uu 权值改为 tt；QMAX u v：询问点 uu 到点 vv 路径上的节点的最大权值；QSUM u v：询问点 uu 到点 vv 路径上的节点的权值和。
注意：从点 uu 到点 vv 路径上的节点包括 uu 和 vv 本身。
输入描述 Input Description
第一行为一个数 nn，表示节点个数；
接下来 n−1n−1 行，每行两个整数 a,ba,b，表示节点 aa 与节点 bb 之间有一条边相连；
接下来 nn 行，每行一个整数，第 ii 行的整数 wiwi 表示节点 ii 的权值；
接下来一行，为一个整数 qq ，表示操作总数；
接下来 qq 行，每行一个操作，以 CHANGE u t 或 QMAX u v 或 QSUM u v的形式给出。
输出描述 Output Description
对于每个 QMAX 或 QSUM 的操作，每行输出一个整数表示要求的结果。
样例输入 Sample Input
4 1 2 2 3 4 1 4 2 1 3 12 QMAX 3 4 QMAX 3 3 QMAX 3 2 QMAX 2 3 QSUM 3 4 QSUM 2 1 CHANGE 1 5 QMAX 3 4 CHANGE 3 6 QMAX 3 4 QMAX 2 4 QSUM 3 4
样例输出 Sample Output
4 1 2 2 10 6 5 6 5 16
数据范围及提示 Data Size & Hint
对于 100%100% 的数据，有 1≤n≤3×104,0≤q≤2×1051≤n≤3×104,0≤q≤2×105。中途操作中保证每个节点的权值 ww 在 −30000−30000 至 3000030000 之间。
代码
这个，经典水题，思路：
这个题目可以使用树状数组来解决。
首先建立一个树状数组，用于存储每个节点的权值。
然后遍历树的每个节点，将节点的权值加入到树状数组中。
接下来处理操作，对于CHANGE操作，直接更新节点的权值即可。
对于QMAX操作，可以通过查询树状数组的前缀最大值来实现。找到节点u和节点v的最近公共祖先，然后分别查询节点u到最近公共祖先的路径上的最大值，和节点v到最近公共祖先的路径上的最大值，取最大值即为所求。
对于QSUM操作，可以通过查询树状数组的前缀和来实现。同样找到节点u和节点v的最近公共祖先，然后分别查询节点u到最近公共祖先的路径上的和，和节点v到最近公共祖先的路径上的和，然后将两者相加即为所求。
时间复杂度分析：建立树状数组的时间复杂度为O(nlogn)，处理操作的时间复杂度为O(qlogn)，总时间复杂度为O(nlogn+qlogn)。由于n和q的最大值为3×10^4和2×10^5，所以算法可以承受。
我喜欢最后附代码
等一下……啊！
保持镇定，分号没加
这才是帅气的作者应有的样子
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
int first[MAXN],nxt[MAXN],to[MAXN],topp=0;
int sum[MAXN*4],maxx[MAXN*4],num[MAXN];
int son[MAXN],father[MAXN],top[MAXN],siz[MAXN],id[MAXN],rk[MAXN],pos=0,dep[MAXN];
int n,m;
void add(int u,int v)
{topp++;nxt[topp]=first[u];first[u]=topp;to[topp]=v;topp++;nxt[topp]=first[v];first[v]=topp;to[topp]=u;
}
void dfs(int x,int deep)//搞好重链
{dep[x]=deep;siz[x]=1;int tmp=0;for(int i=first[x];~i;i=nxt[i]){int v=to[i];if(father[x]==v) continue;father[v]=x;dfs(v,deep+1);siz[x]+=siz[v];if(siz[v]>tmp) son[x]=v,tmp=siz[v];}return ;
}
void dfs2(int x,int nowtop)//id节点所对应后的编号 rk序列所对应的数字 top
{top[x]=nowtop;pos++;id[x]=pos;rk[pos]=x;if(!son[x]) return;dfs2(son[x],nowtop);for(int i=first[x];~i;i=nxt[i]){int v=to[i];if(v==father[x]||v==son[x]){continue;}dfs2(v,v);}return ;
}
void build(int root,int l,int r)
{
// cout<<l<<" "<<r<<endl;if(l==r){maxx[root]=num[rk[l]];sum[root]=num[rk[l]];//cout<<maxx[root]<<" "<<sum[root]<<num[r<<endl;return ;}int mid=(l+r)/2;build(root*2,l,mid);build(root*2+1,mid+1,r);maxx[root]=max(maxx[root*2],maxx[root*2+1]);sum[root]=sum[root*2]+sum[root*2+1];
// cout<<maxx[root]<<" "<<sum[root]<<endl;return ;
}
void updata(int root,int l,int r,int x,int num)
{
// cout<<l<<" "<<r<<endl;if(l==r&&r==x){maxx[root]=num;sum[root]=num;return;}int mid=(l+r)/2;if(x<=mid){updata(root*2,l,mid,x,num);}else{updata(root*2+1,mid+1,r,x,num);}maxx[root]=max(maxx[root*2],maxx[root*2+1]);sum[root]=sum[root*2]+sum[root*2+1];
}
int qqmax(int root,int ll,int rr,int l,int r)
{if(ll<=l&&rr>=r){return maxx[root];}int mid=(l+r)/2;if(rr<=mid) return qqmax(root*2,ll,rr,l,mid);else if(ll>mid) return qqmax(root*2+1,ll,rr,mid+1,r);else return max(qqmax(root*2,ll,rr,l,mid),qqmax(root*2+1,ll,rr,mid+1,r));
}
int qqsum(int root,int ll,int rr,int l,int r)
{if(ll<=l&&rr>=r){return sum[root];}int mid=(l+r)/2;if(rr<=mid) return qqsum(root*2,ll,rr,l,mid);else if(ll>mid) return qqsum(root*2+1,ll,rr,mid+1,r);else return qqsum(root*2,ll,rr,l,mid)+qqsum(root*2+1,ll,rr,mid+1,r);
}
int qmax(int x,int y)
{int ans=-1e9;while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]]){ans=max(ans,qqmax(1,id[top[y]],id[y],1,n));y=father[top[y]];}else{ans=max(ans,qqmax(1,id[top[x]],id[x],1,n));x=father[top[x]];}}
// cout<<"x"<<endl;if(x==y){ans=max(ans,num[x]);}if(dep[x]<dep[y]){ans=max(ans,qqmax(1,id[x],id[y],1,n));}if(dep[x]>dep[y]){ans=max(ans,qqmax(1,id[y],id[x],1,n));}return ans;
}
int qsum(int x,int y)
{int ans=0;while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]]){ans+=qqsum(1,id[top[y]],id[y],1,n);y=father[top[y]];}else{ans+=qqsum(1,id[top[x]],id[x],1,n);x=father[top[x]];}}if(x==y){ans+=num[x];}if(dep[x]<dep[y]){ans+=qqsum(1,id[x],id[y],1,n);}if(dep[x]>dep[y]){ans+=qqsum(1,id[y],id[x],1,n);}return ans;
}
int main()
{father[1]=1;memset(first,-1,sizeof(first));scanf("%d",&n);for(int i=1;i<n;i++){int tmp1,tmp2;scanf("%d%d",&tmp1,&tmp2);add(tmp1,tmp2);}for(int i=1;i<=n;i++){scanf("%d",&num[i]);}dfs(1,1);dfs2(1,1);build(1,1,n);
// cout<<qqsum(1,1,4,1,4);scanf("%d",&m);while(m--){char op[20];scanf("%s",op);int tmp1,tmp2;scanf("%d%d",&tmp1,&tmp2);if(op[1]=='H')//更新节点{num[tmp1]=tmp2;updata(1,1,n,id[tmp1],tmp2);}if(op[1]=='M')//最大值{printf("%d\n",qmax(tmp1,tmp2));}if(op[1]=='S')//求和{printf("%d\n",qsum(tmp1,tmp2));}}
}
