```
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
const int maxx=1e5+5;
struct node{ long long l,r,he,lazy,max; } tree[4*maxx];
long long num=0,top[maxx],belong[maxx],numm[maxx],fa[maxx]={0},deep[maxx]={0},what[maxx];
long long sonnum[maxx]={0},hson[maxx]={0};
long long Num=0,begin[maxx],end[maxx];//链的信息
long long trbegin[maxx],trend[maxx];//节点子树
bool vis[maxx]={0};
int v[maxx];
vector<int> e[maxx];
vector<int> tr[maxx];
void add(int x,int y){ e[x].push_back(y),e[y].push_back(x); }
void dfs(int x)
{
vis[x]=1;
//cout<<1<<endl;
for(int i=0;i<e[x].size();i++)
if(!vis[e[x][i]])
tr[x].push_back(e[x][i]),dfs(e[x][i]);
}
int dfs1(int x,int father,int deeps)
{
//cout<<2;
//cout<<" "<<x<<" "<<tr[x].size()<<endl;
fa[x]=father,deep[x]=deeps;
int maxnum=0,maxson=0,Sonnum=1;
for(int i=0;i<tr[x].size();i++)
{
Sonnum+=dfs1(tr[x][i],x,deeps+1);
if(sonnum[tr[x][i]]>maxnum) maxson=tr[x][i],maxnum=sonnum[tr[x][i]];
}
hson[x]=maxson;
sonnum[x]=Sonnum;
return Sonnum;
}
void dfs2(int x,int NUM,int Top)
{
//cout<<3<<endl;
int c;
belong[x]=NUM,top[x]=Top,numm[x]=++num,trbegin[x]=num,what[num]=x;
if(tr[x].size()==0)
{
trend[x]=num;
end[NUM]=num;
return;
}
dfs2(hson[x],NUM,Top);
for(int i=0;i<tr[x].size();i++)
if(tr[x][i]!=hson[x]) c=++Num,dfs2(tr[x][i],Num,tr[x][i]),begin[c]=numm[tr[x][i]];
trend[x]=num;
}
void build(int id,int l,int r)
{
tree[id].l=l,tree[id].r=r;
if(l==r)
{
//cout<<v[what[l]]<<" "<<id<<" "<<11223<<endl;
tree[id].he=v[what[l]];
tree[id].max=v[what[l]];
return;
}
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
tree[id].he=tree[id*2].he+tree[id*2+1].he;
tree[id].max=max(tree[id*2].max,tree[id*2+1].max);
}
void query(int id,int l,int r,long long lazy)
{
//cout<<1<<endl;
if(tree[id].l==l&&tree[id].r==r)
{
tree[id].he=lazy;
tree[id].max=lazy;
return;
}
if(r<=tree[2*id].r) query(id*2,l,r,lazy);
else if(l>=tree[2*id+1].l) query(id*2+1,l,r,lazy);
else query(id*2,l,tree[2*id].r,lazy),query(id*2+1,tree[2*id+1].l,r,lazy);
tree[id].he=tree[id*2].he+tree[id*2+1].he;
tree[id].max=max(tree[id*2].max,tree[id*2+1].max);
}
long long getans(int id,int l,int r)
{
if(tree[id].l==l&&tree[id].r==r) return tree[id].he;
if(r<=tree[2*id].r) return getans(id*2,l,r);
else if(l>=tree[2*id+1].l) return getans(id*2+1,l,r);
else return getans(id*2,l,tree[2*id].r)+getans(id*2+1,tree[2*id+1].l,r);
}
long long getmax(int id,int l,int r)
{
if(tree[id].l==l&&tree[id].r==r) return tree[id].max;
if(r<=tree[2*id].r) return getmax(id*2,l,r);
else if(l>=tree[2*id+1].l) return getmax(id*2+1,l,r);
else return max(getmax(id*2,l,tree[2*id].r),getmax(id*2+1,tree[2*id+1].l,r));
}
int main(int argc, char** argv) {
long long n,a,b,m;//cout<<1<<endl;
scanf("%lld",&n);//cout<<1<<endl;
for(int i=1;i<=n-1;i++) scanf("%lld%lld",&a,&b),add(a,b);//cout<<1<<endl;
for(int i=1;i<=n;i++) scanf("%lld",&v[i]);//cout<<1<<endl;
scanf("%lld",&m);//cout<<1<<endl;
dfs(1),dfs1(1,0,1),dfs2(1,0,1);//cout<<111<<endl;
build(1,1,n);
//for(int i=1;i<=n;i++) cout<<numm[i]<<" "<<belong[i]<<" "<<fa[i]<<" "<<trbegin[i]<<" "<<trend[i]<<endl;
//for(int i=1;i<=n;i++) cout<<v[i]<<endl;
//for(int i=1;i<=20;i++) cout<<tree[i].l<<" "<<tree[i].r<<" "<<tree[i].he<<endl;
while(m--)
{
long long ans=0;
string ask;
cin>>ask;
scanf("%lld",&a);
if(ask[1]=='H')
{
//cout<<3<<endl;
scanf("%lld",&b);
query(1,numm[a],numm[a],b);
//for(int i=1;i<=20;i++) cout<<tree[i].l<<" "<<tree[i].r<<" "<<tree[i].he<<endl;
}
if(ask[1]=='M')
{
scanf("%lld",&b);
while(belong[a]!=belong[b])
if(deep[what[begin[belong[a]]]]>=deep[what[begin[belong[b]]]])
ans=getmax(1,begin[belong[a]],numm[a]),a=fa[what[begin[belong[a]]]];
else
ans=getmax(1,begin[belong[b]],numm[b]),b=fa[what[begin[belong[b]]]];
//cout<<a<<" "<<numm[a]<<endl;
ans=getmax(1,min(numm[a],numm[b]),max(numm[a],numm[b]));
printf("%lld\n",ans);
}
if(ask[1]=='S')
{
scanf("%lld",&b);
while(belong[a]!=belong[b])
if(deep[what[begin[belong[a]]]]>=deep[what[begin[belong[b]]]])
ans+=getans(1,begin[belong[a]],numm[a]),a=fa[what[begin[belong[a]]]];
else
ans+=getans(1,begin[belong[b]],numm[b]),b=fa[what[begin[belong[b]]]];
//cout<<a<<" "<<numm[a]<<endl;
ans+=getans(1,min(numm[a],numm[b]),max(numm[a],numm[b]));
printf("%lld\n",ans);
}
}
return 0;
}/*
int main()
{
cout<<1;
return 0;
}*/
```
by love2076328848 @ 2018-04-23 22:43:02
$ \color{white} \colorbox{brown}{\textbf{「禁忌」四重 }O2 \textbf{优化} } $
好吧不闹了
@[love2076328848](/space/show?uid=73677)
处理QMax时
过程中ans没有取max，而且ans初值应该为负无穷大
by Night_Aurora @ 2018-04-24 10:22:03
謝謝
by love2076328848 @ 2018-04-24 17:35:44