入门题 + 熟悉代码
/**************************************************************
Problem: 1036
User: 96655
Language: C++
Result: Accepted
Time:2472 ms
Memory:5536 kb
****************************************************************/ #include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<iostream>
#include<cstdlib>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#include<stack>
#include<utility>
using namespace std;
const int maxn=;
struct Edge
{
int v,next;
} edge[maxn*];
int va[maxn],p,head[maxn],clk,n;
void init()
{
memset(head,-,sizeof(head));
p=clk=;
}
void addedge(int u,int v)
{
edge[p].v=v;
edge[p].next=head[u];
head[u]=p++;
}
int id[maxn],sz[maxn],dep[maxn],fa[maxn],son[maxn],top[maxn];
int xx[maxn];
void dfs1(int u,int f,int d)
{
dep[u]=d;
fa[u]=f;
sz[u]=;
son[u]=-;
for(int i=head[u]; ~i; i=edge[i].next)
{
int v=edge[i].v;
if(v==f)continue;
dfs1(v,u,d+);
sz[u]+=sz[v];
if(son[u]==-||sz[v]>sz[son[u]])
son[u]=v;
}
}
void dfs2(int u,int tp)
{
id[u]=++clk;
xx[id[u]]=va[u];
top[u]=tp;
if(son[u]!=-)dfs2(son[u],tp);
for(int i=head[u]; ~i; i=edge[i].next)
{
int v=edge[i].v;
if(v==fa[u]||v==son[u])continue;
dfs2(v,v);
}
}
int sum[maxn*],maxv[maxn*];
void pushup(int rt)
{
sum[rt]=sum[rt*]+sum[rt*+];
maxv[rt]=max(maxv[rt*],maxv[rt*+]);
}
void build(int rt,int l,int r)
{
if(l==r)
{
sum[rt]=maxv[rt]=xx[l];
return;
}
int m=(l+r)>>;
build(rt*,l,m);
build(rt*+,m+,r);
pushup(rt);
}
void update(int rt,int l,int r,int pos,int c)
{
if(l==r)
{
maxv[rt]=sum[rt]=c;
return;
}
int m=(l+r)>>;
if(pos<=m)update(rt*,l,m,pos,c);
else update(rt*+,m+,r,pos,c);
pushup(rt);
}
int query1(int rt,int l,int r,int x,int y)
{
if(x<=l&&r<=y)
{
return sum[rt];
}
int ans=;
int m=(l+r)>>;
if(x<=m)ans+=query1(rt*,l,m,x,y);
if(y>m)ans+=query1(rt*+,m+,r,x,y);
return ans;
}
int query2(int rt,int l,int r,int x,int y)
{
if(x<=l&&r<=y)
{
return maxv[rt];
}
int ans=-;
int m=(l+r)>>;
if(x<=m)ans=max(ans,query2(rt*,l,m,x,y));
if(y>m)ans=max(ans,query2(rt*+,m+,r,x,y));
return ans;
}
int getsum(int u,int v)
{
int ans=;
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]])
swap(u,v);
ans+=query1(,,n,id[top[u]],id[u]);
u=fa[top[u]];
}
if(dep[u]>dep[v])swap(u,v);
ans+=query1(,,n,id[u],id[v]);
return ans;
}
int getmax(int u,int v)
{
int ans=-;
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]])
swap(u,v);
ans=max(ans,query2(,,n,id[top[u]],id[u]));
u=fa[top[u]];
}
if(dep[u]>dep[v])swap(u,v);
ans=max(ans,query2(,,n,id[u],id[v]));
return ans;
}
int main()
{
while(~scanf("%d",&n))
{
init();
for(int i=; i<n; ++i)
{
int u,v;
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
}
for(int i=; i<=n; i++)
scanf("%d",&va[i]);
dfs1(,,);
dfs2(,);
build(,,n);
int q;
scanf("%d",&q);
while(q--)
{
char s[];
int x,y;
scanf("%s%d%d",s,&x,&y);
if(s[]=='Q')
{
if(s[]=='M') printf("%d\n",getmax(x,y));
else printf("%d\n",getsum(x,y));
}
else update(,,n,id[x],y);
}
}
return ;
}