题目大意:一棵树上有n个节点,编号分别为1到n,每个节点都有一个权值w。有一些操作:1.把结点u的权值改为t;2.询问从点u到点v的路径上的节点的最大权值 3.询问从点u到点v的路径上的节点的权值和。
思路:进行轻重树链剖分,再根据每个节点的dfs序建立线段树,维护其最大值以及和,询问时用树剖后的结果将重链作为区间一段一段求和。
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#define M 1000009
using namespace std;
int n,dfn,cnt,to[M],next[M],head[M],size[M],vis[M],deep[M],fa[M],top[M],w[M],mx[M],sum[M],id[M];
void add(int x,int y)
{
to[++cnt]=y,next[cnt]=head[x],head[x]=cnt;
}
void dfs1(int x)
{
size[x]=vis[x]=1;
for (int i=head[x];i;i=next[i])
if (!vis[to[i]])
{
deep[to[i]]=deep[x]+1;
fa[to[i]]=x;
dfs1(to[i]);
size[x]+=size[to[i]];
}
}
void dfs2(int x,int chain)
{
int k=0,i;
id[x]=++dfn;
top[x]=chain;
for (i=head[x];i;i=next[i])
if (deep[to[i]]>deep[x] && size[to[i]]>size[k]) k=to[i];
if (!k) return;
dfs2(k,chain);
for (i=head[x];i;i=next[i])
if (deep[to[i]]>deep[x] && to[i]!=k) dfs2(to[i],to[i]);
}
int LCA(int x,int y)
{
for (;top[x]!=top[y];x=fa[top[x]])
if (deep[top[x]]<deep[top[y]]) swap(x,y);
return deep[x]<deep[y]?x:y;
}
void change(int l,int r,int x,int y,int cur)
{
if (l==r)
{
mx[cur]=sum[cur]=y;
return;
}
int mid=l+r>>1;
if (x<=mid) change(l,mid,x,y,cur<<1);
else change(mid+1,r,x,y,cur<<1|1);
mx[cur]=max(mx[cur<<1],mx[cur<<1|1]);
sum[cur]=sum[cur<<1]+sum[cur<<1|1];
}
int SUM(int L,int R,int l,int r,int cur)
{
if (l<=L && r>=R) return sum[cur];
int mid=L+R>>1;
if (l>mid) return SUM(mid+1,R,l,r,cur<<1|1);
else if (r<=mid) return SUM(L,mid,l,r,cur<<1);
else return SUM(L,mid,l,r,cur<<1)+SUM(mid+1,R,mid+1,r,cur<<1|1);
}
int MAX(int L,int R,int l,int r,int cur)
{
if (l<=L && r>=R) return mx[cur];
int mid=L+R>>1;
if (l>mid) return MAX(mid+1,R,l,r,cur<<1|1);
else if (r<=mid) return MAX(L,mid,l,r,cur<<1);
else return max(MAX(L,mid,l,mid,cur<<1),MAX(mid+1,R,mid+1,r,cur<<1|1));
}
int Sum(int x,int y)
{
int ans=0;
for (;top[x]!=top[y];x=fa[top[x]])
{
if (deep[top[x]]<deep[top[y]]) swap(x,y);
ans+=SUM(1,n,id[top[x]],id[x],1);
}
if (deep[x]>deep[y]) swap(x,y);
return ans+SUM(1,n,id[x],id[y],1);
}
int Max(int x,int y)
{
int ans=-999999999;
for (;top[x]!=top[y];x=fa[top[x]])
{
if (deep[top[x]]<deep[top[y]]) swap(x,y);
ans=max(ans,MAX(1,n,id[top[x]],id[x],1));
}
if (deep[x]>deep[y]) swap(x,y);
return max(ans,MAX(1,n,id[x],id[y],1));
}
int main()
{
int m,i,x,y;
scanf("%d",&n);
for (i=1;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
dfs1(1);
dfs2(1,1);
for (i=1;i<=n;i++) scanf("%d",&w[i]),change(1,n,id[i],w[i],1);
scanf("%d",&m);
for (i=1;i<=m;i++)
{
char ch[9];
scanf("%s%d%d",ch,&x,&y);
if (ch[0]=='C') w[x]=y,change(1,n,id[x],y,1);
else
if (ch[1]=='S') printf("%d\n",Sum(x,y));
else printf("%d\n",Max(x,y));
}
return 0;
}