思路

就是树链剖分+线段树的板子，但是因为眼疾看少了”多组数据“导致一直WA（哭了 不会的可以看一下我的这篇博客：https://editor.csdn.net/md/?articleId=121182009

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int N=6e4+7;

//int read(){	int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
int sz[N],fa[N],son[N],dep[N],dfn[N],bel[N],idfn[N],idx=0;
vector<int>G[N];

void dfs1(int x){
	sz[x]=1;
	for(int i=0;i<G[x].size();i++){
		int to=G[x][i];
		if(to==fa[x]) continue;
		fa[to]=x;
		dep[to]=dep[x]+1;
		dfs1(to);
		sz[x]+=sz[to];
		if(sz[son[x]]<sz[to]) son[x]=to;
	}
}

void dfs2(int x,int tp){
	dfn[x]=++idx;
	idfn[idx]=x;
	bel[x]=tp;
	if(son[x]) dfs2(son[x],tp); 
	for(int i=0;i<G[x].size();i++){
		int to=G[x][i];
		if(to==fa[x]||to==son[x]) continue;
		dfs2(to,to);
	}
}

int tr[N<<2],mx[N<<2],val[N];

void build(int p,int l,int r){
	if(l==r){
		tr[p]=mx[p]=val[idfn[l]];
		return;
	}
	int mid=l+r>>1; 
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	tr[p]=tr[p<<1]+tr[p<<1|1];
	mx[p]=max(mx[p<<1],mx[p<<1|1]);
}

void update(int p,int l,int r,int pos,int num){
	if(l==r){
		tr[p]=mx[p]=num;
		return;
	}
	int mid=l+r>>1;
	if(pos<=mid) update(p<<1,l,mid,pos,num);
	else update(p<<1|1,mid+1,r,pos,num);
	tr[p]=tr[p<<1]+tr[p<<1|1];
	mx[p]=max(mx[p<<1],mx[p<<1|1]);
}

int qsm(int p,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr) return tr[p];
	int res=0,mid=l+r>>1;
	if(ql<=mid) res+=qsm(p<<1,l,mid,ql,qr);
	if(qr>mid) res+=qsm(p<<1|1,mid+1,r,ql,qr);
	return res;
}

int qmx(int p,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr) return mx[p];
	int res=-inf,mid=l+r>>1;
	if(ql<=mid) res=max(res,qmx(p<<1,l,mid,ql,qr));
	if(qr>mid) res=max(res,qmx(p<<1|1,mid+1,r,ql,qr));
	return res;
}

void init(int n){
	for(int i=1;i<=n;i++){
		G[i].clear();
		fa[i]=son[i]=dep[i]=sz[i]=bel[i]=idfn[i]=0;
	}
	idx=0;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int n,q,u,v,op,x,y;
	while(cin>>n>>q){
		init(n);
		for(int i=1;i<=n;i++) cin>>val[i];
		for(int i=2;i<=n;i++){
			cin>>u>>v;
			G[u].push_back(v);
			G[v].push_back(u);
		}
		dfs1(1);
		dfs2(1,1);
		build(1,1,n);
		for(int i=1;i<=q;i++){
			cin>>op>>x>>y;
			if(op==0){
				int res=-inf;
				while(bel[x]!=bel[y]){
					if(dep[bel[x]]<dep[bel[y]]) swap(x,y);
					res=max(res,qmx(1,1,n,dfn[bel[x]],dfn[x]));
					x=fa[bel[x]];
				}
				if(dep[x]<dep[y]) swap(x,y);
				res=max(res,qmx(1,1,n,dfn[y],dfn[x]));
				cout<<res<<"\n";
			}else if(op==1){
				int res=0;
				while(bel[x]!=bel[y]){
					if(dep[bel[x]]<dep[bel[y]]) swap(x,y);
					res+=qsm(1,1,n,dfn[bel[x]],dfn[x]);
					x=fa[bel[x]];
				}
				if(dep[x]<dep[y]) swap(x,y);
				res+=qsm(1,1,n,dfn[y],dfn[x]);
				cout<<res<<"\n";
			}else{
				update(1,1,n,dfn[x],y);
			}
		}
	}
	return 0;
}