C++11(clang++ 3.9) 解法, 执行用时: 678ms, 内存消耗: 15664K, 提交时间: 2020-07-30 11:14:53

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
const int N=30303,mn=-1e9;
int a[N];
int child[N*2],pre[N*2],now[N];
int size[N],mx[N],f[N],dep[N];
int top[N],dfn[N],idfn[N];
int n,m,tot,t;
struct AC{
	int sum,mx;
}tree[N*8];
void ad(int x,int y){
	pre[++tot]=now[x];
	child[tot]=y;
	now[x]=tot;
}
void dfs1(int x,int rt){
	size[x]=1;
	for (int i=now[x]; i; i=pre[i]){
		int son=child[i];
		if (son==rt)	continue;
		dep[son]=dep[x]+1;
		f[son]=x;
		dfs1(son,x);
		size[x]=size[x]+size[son];
		if (size[mx[x]]<size[son])	mx[x]=son;
	}
}
void dfs2(int x,int rt){
	top[x]=rt;
	dfn[x]=++t,idfn[t]=x;
	if (mx[x])	dfs2(mx[x],rt);
	for (int i=now[x]; i; i=pre[i]){
		int son=child[i];
		if (f[x]==son||mx[x]==son)	continue;
		dfs2(son,son);
	}
}
AC update(AC x,AC y){
	return (AC){x.sum+y.sum,max(x.mx,y.mx)};
}
void build(int p,int l,int r){
	if (l==r){
		tree[p].mx=tree[p].sum=a[idfn[l]];
		return;
	}
	int mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	tree[p]=update(tree[p*2],tree[p*2+1]);
}
void modify(int p,int l,int r,int a,int b){
	if (l==r){
		tree[p].mx=tree[p].sum=b;
		return;
	}
	int mid=(l+r)>>1;
	if (a<=mid)	modify(p*2,l,mid,a,b);
	else modify(p*2+1,mid+1,r,a,b);
	tree[p]=update(tree[p*2],tree[p*2+1]);
}
AC find(int p,int l,int r,int a,int b){
	if (a<=l&&r<=b)	return tree[p];
	int mid=(l+r)>>1;
	AC f1=(AC){0,mn},f2=(AC){0,mn};
	if (a<=mid)	f1=find(p*2,l,mid,a,b);
	if (b>mid)	f2=find(p*2+1,mid+1,r,a,b);
	return update(f1,f2);
}

AC query(int x,int y){
	AC ans=(AC){0,mn};
	while (top[x]!=top[y]){
		if (dep[top[x]]<dep[top[y]])	swap(x,y);
		ans=update(ans,find(1,1,n,dfn[top[x]],dfn[x]));
		x=f[top[x]];
	}
	if (dep[x]<dep[y])	swap(x,y);
	return update(ans,find(1,1,n,dfn[y],dfn[x]));
}
int main(){
	int o,x,y;
	while (scanf("%d%d",&n,&m)!=EOF){
		tot=t=0;
		for (int i=1; i<=n; i++)	mx[i]=now[i]=0;
		for (int i=1; i<=n; i++)
			scanf("%d",&a[i]);
		for (int i=1; i<n; i++){
			scanf("%d%d",&x,&y);
			ad(x,y);
			ad(y,x);
		}
		dfs1(1,0);
		dfs2(1,1);
		build(1,1,n);
		for (int i=1; i<=m; i++){
			scanf("%d%d%d",&o,&x,&y);
			if (o==0)	printf("%d\n",query(x,y).mx);
			if (o==1)	printf("%d\n",query(x,y).sum);
			if (o==2)	modify(1,1,n,dfn[x],y);
		}
	}
	return 0;
}