树的统计照着题解敲的板子似乎越界了,求解……我可能瞎了
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const long long maxn=200010;
long long n,m,e,beg[maxn],nex[maxn],to[maxn],w[maxn],wt[maxn],a[maxn<<2],b[maxn<<2],son[maxn],id[maxn],fa[maxn],cnt,dep[maxn],siz[maxn],top[maxn],res=0;
inline void add(long long x,long long y)
{
to[++e]=y;
nex[e]=beg[x];
beg[x]=e;
}
inline void build(long long rt,long long l,long long r)
{
if(l==r)
{
a[rt]=wt[l];
b[rt]=wt[l];
return ;
}
build(rt<<1,l,((l+r)>>1));
build(rt<<1|1,((l+r)>>1)+1,r);
a[rt]=a[rt<<1]+a[rt<<1|1];
b[rt]=max(b[rt<<1],b[rt<<1|1]);
}
inline void query(long long rt,long long l,long long r,long long L,long long R)
{
if(L<=l&&r<=R)
{
res+=a[rt];
return ;
}
else{
if(L<=((l+r)>>1)) query(rt<<1,l,((l+r)>>1),L,R);
if(R>((l+r)>>1)) query(rt<<1|1,((l+r)>>1)+1,r,L,R);
}
}
inline void quemax(long long rt,long long l,long long r,long long L,long long R)
{
if(L<=l&&r<=R)
{
res=max(b[rt],res);
return ;
}
else
{
if(L<=((l+r)>>1)) quemax(rt<<1,l,((l+r)>>1),L,R);
if(R>((l+r)>>1)) quemax(rt<<1|1,((l+r)>>1)+1,r,L,R);
}
}
inline void update(long long rt,long long l,long long r,long long L,long long R,long long k)
{
if(L<=l&&r<=R)
{
a[rt]=k;
b[rt]=k;
}
else
{
if(L<=((l+r)>>1)) update(rt<<1,l,((l+r)>>1),L,R,k);
if(R>((l+r)>>1)) update(rt<<1|1,((l+r)>>1)+1,r,L,R,k);
a[rt]=(a[rt<<1]+a[rt<<1|1]);
b[rt]=max(b[rt<<1],b[rt<<1|1]);
}
}
inline long long qRange(long long x,long long y)
{
long long ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
res=0;
query(1,1,n,id[top[x]],id[x]);
ans+=res;
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
res=0;
query(1,1,n,id[x],id[y]);
ans+=res;
return ans;
}
inline long long qMax(long long x,long long y)
{
long long ans=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
res=0;
quemax(1,1,n,id[top[x]],id[x]);
ans=max(ans,res);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
res=0;
quemax(1,1,n,id[x],id[y]);
ans=max(ans,res);
return ans;
}
inline void updSon(long long x,long long k) {update(1,1,n,id[x],id[x],k);}
inline void dfs1(long long x,long long f,long long deep)
{
dep[x]=deep;
fa[x]=f;
siz[x]=1;
long long maxson=-1;
for(register long long i=beg[x];i;i=nex[i])
{
long long y=to[i];
if(y==f) continue;
dfs1(y,x,deep+1);
siz[x]+=siz[y];
if(siz[y]>maxson)
{
son[x]=y,maxson=siz[y];
}
}
}
inline void dfs2(long long x,long long topf)
{
id[x]=++cnt;
wt[cnt]=w[x];
top[x]=topf;
if(!son[x]) return ;
dfs2(son[x],topf);
for(register long long i=beg[x];i;i=nex[i])
{
long long y=to[i];
if(y==fa[x]||y==son[x]) continue;
dfs2(y,y);
}
}
int main()
{
scanf("%lld",&n);
for(register long long i=1;i<n;i++)
{
long long a,b;
scanf("%lld%lld",&a,&b);
add(a,b);add(b,a);
}
for(register long long i=1;i<=n;i++) scanf("%lld",&w[i]);
dfs1(1,1,1);
dfs2(1,1);
build(1,1,n);
scanf("%lld",&m);
while(m--)
{
long long x,y;
char k[10];
cin>>k;
if(k[1]=='H')
{
scanf("%lld%lld",&x,&y);
updSon(x,y);
}
else if(k[1]=='S')
{
scanf("%lld%lld",&x,&y);
printf("%lld\n",qRange(x,y));
}
else
{
scanf("%lld%lld",&x,&y);
printf("%lld\n",qMax(x,y));
}
}
return 0;
}