6977 树的统计
经验值：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));
}
}
}