题目
分析
首先，将这些节点按dfs序建一棵线段树。
因为按dfs序，所以在同一子树上的节点会放在线段树相邻的位置。
发现，对于一个位置x，它的权值只会对以x为根的子树造成影响。
当修改x时，用w[x]更新子树x的最大值，
接着从x向上跳，用w[fa[x]]更新子树fa[x]-子树x最大值，
因为当用w[fa[x]]来更新过子树fa[x]-子树x时，再用它更新就会没有意义，所以打个标记，不再更新。这样就最多只会更新n次。
#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
const int N=100005;
using namespace std;
int d[N],aft[N],fa[N],mx[N*10],son[N],size[N],n,m,last[N*2],next[N*2],to[N*2],tot,v1[N],ans,end[N],lazy[N*10];
int bz[N];
int bj(int x,int y)
{
next[++tot]=last[x];
last[x]=tot;
to[tot]=y;
}
int down(int v)
{
if(!lazy[v]) return 0;
lazy[v*2]=max(lazy[v],lazy[v*2]);
lazy[v*2+1]=max(lazy[v],lazy[v*2+1]);
mx[v*2]=max(mx[v*2],lazy[v]);
mx[v*2+1]=max(mx[v*2+1],lazy[v]);
}
int dg(int x)
{
d[++tot]=x;
aft[x]=tot;
for(int i=last[x];i;i=next[i])
{
int j=to[i];
if(j!=fa[x])
{
fa[j]=x;
dg(j);
end[j]=tot;
}
}
}
int change(int v,int l,int r,int x,int y,int z)
{
if(x>y && x && y) return 0;
if(l==x && y==r)
{
mx[v]=max(mx[v],z);
lazy[v]=max(lazy[v],z);
return 0;
}
down(v);
int mid=(l+r)/2;
if(y<=mid) change(v*2,l,mid,x,y,z);
else
if(x>mid) change(v*2+1,mid+1,r,x,y,z);
else change(v*2,l,mid,x,mid,z),change(v*2+1,mid+1,r,mid+1,y,z);
mx[v]=max(mx[v*2],mx[v*2+1]);
}
int find(int v,int l,int r,int x)
{
if(l==r) return mx[v];
down(v);
int mid=(l+r)/2,j;
if(x<=mid) j=find(v*2,l,mid,x);
else j=find(v*2+1,mid+1,r,x);
mx[v]=max(mx[v*2],mx[v*2+1]);
return j;
}
int up(int x)
{
if(!fa[x]) return 0;
change(1,1,tot,max(aft[fa[x]],1),aft[x]-1,v1[fa[x]]);
change(1,1,tot,end[x]+1,end[fa[x]],v1[fa[x]]);
if(!bz[x]) up(fa[x]);
bz[x]=true;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&v1[i]);
for(int i=1;i<=n-1;i++)
{
int x,y;
scanf("%d%d",&x,&y);
bj(x,y);
bj(y,x);
}
tot=0;
dg(1);
end[1]=tot;
for(int i=1;i<=m;i++)
{
char c=getchar();
int x;
while(c!='Q' && c!='M') c=getchar();
if(c=='M')
{
scanf("odify %d",&x);
change(1,1,tot,aft[x],end[x],v1[x]);
up(x);
}
else
{
scanf("uery %d",&x);
ans=find(1,1,tot,aft[x]);
printf("%d\n",(ans)?ans:-1);
}
}
}