思路是找次大值作为答案，用 树链剖分+multiset 维护，AC on #2 #4 #6

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e5+10;
int n,m,w[N];
struct edge{
	int v,next;
}edges[N<<1];
int head[N],idx;
int fa[N],siz[N],dep[N],son[N],dfn[N],rev[N],top[N];

void add_edge(int u,int v){
	idx++;
	edges[idx].v=v;
	edges[idx].next=head[u];
	head[u]=idx;
	return;
}
struct Segment_tree{
	#define ls o<<1
	#define rs o<<1|1
	#define mid (l+r>>1)
	int tmax[N<<2],ttmax[N<<2];
	void pushup(int o){ 				// 更新信息
		tmax[o]=max(tmax[ls],tmax[rs]);
		ttmax[o]=(tmax[ls]==tmax[rs])?max(ttmax[ls],ttmax[rs]):min(tmax[ls],tmax[rs]);
		return;
	}
	void build(int o,int l,int r){ 					// 建树
		if(l==r){
			tmax[o]=w[rev[l]];
			return;
		}
		build(ls,l,mid);build(rs,mid+1,r);
		pushup(o);
		return;
	}
	void modify(int o,int l,int r,int id,int k){ 			// 更新
		if(l==r){
			tmax[o]+=k;
			return;
		}
		if(id<=mid)modify(ls,l,mid,id,k);
		else modify(rs,mid+1,r,id,k);
		pushup(o);
		return;
	}
	int querymax(int o,int l,int r,int s,int t){
		if(s<=l&&r<=t)return tmax[o];
		int ret=0;
		if(s<=mid)ret=querymax(ls,l,mid,s,t);
		if(mid<t)ret=max(ret,querymax(rs,mid+1,r,s,t));
		return ret;
	}
	int querytmax(int o,int l,int r,int s,int t){ 				// 查询次大值
		if(s<=l&&r<=t)return ttmax[o];
		bool bls=(s<=mid),brs=(mid<t);
		if(bls&&brs){
			int maxls=querymax(ls,l,mid,s,t);
			int maxrs=querymax(rs,mid+1,r,s,t);
			int tmaxls=querytmax(ls,l,mid,s,t);
			int tmaxrs=querytmax(rs,mid+1,r,s,t);
			return (maxls==maxrs)?max(tmaxls,tmaxrs):min(maxls,maxrs);
		}
		else if(bls)return querytmax(ls,l,mid,s,t);
		else if(brs)return querytmax(rs,mid+1,r,s,t);
		return 0;
	}
}tree;

void dfs1(int u,int father){ 					//求前四个
	fa[u]=father;
	siz[u]=1;
	dep[u]=dep[father]+1;
	for(int i=head[u];i;i=edges[i].next){
		int v=edges[i].v;
		if(v==father)continue;
		dfs1(v,u);
		if(siz[son[u]]<siz[v])son[u]=v;
		siz[u]+=siz[v];
	}
	return;
}
int dfncnt;
void dfs2(int u,int tp){ 					// 求后三个
	dfn[u]=++dfncnt;
	rev[dfn[u]]=u;
	top[u]=tp;
	if(!son[u])return;
	dfs2(son[u],tp);
	for(int i=head[u];i;i=edges[i].next){
		int v=edges[i].v;
		if(v==fa[u]||v==son[u])continue;
		dfs2(v,v);
	}
	return;
}

multiset<int>st;

struct node{
	int tmax,ttmax;
	node(){tmax=ttmax=0;}
};

node Qnode(int x,int y){
	node ret;
	int fx=top[x],fy=top[y];
	while(fx!=fy){
		if(dep[fx]<dep[fy])swap(fx,fy),swap(x,y);
		int nowmax=tree.querymax(1,1,n,dfn[fx],dfn[x]),nowtmax=tree.querytmax(1,1,n,dfn[fx],dfn[x]);
		if(nowmax>ret.tmax){
			ret.ttmax=max(nowtmax,ret.tmax);
			ret.tmax=nowmax;
		}
		else if(nowmax!=ret.tmax)ret.ttmax=max(ret.ttmax,nowmax);
		else ret.ttmax=max(ret.ttmax,nowtmax);
		x=fa[fx];fx=top[x];
	}
	if(dfn[x]>dfn[y])swap(x,y);
	int nowmax=tree.querymax(1,1,n,dfn[x],dfn[y]),nowtmax=tree.querytmax(1,1,n,dfn[x],dfn[y]);
	if(nowmax>ret.tmax){
		ret.ttmax=max(nowtmax,ret.tmax);
		ret.tmax=nowmax;
	}
	else if(nowmax!=ret.tmax)ret.ttmax=max(ret.ttmax,nowmax);
	else ret.ttmax=max(ret.ttmax,nowtmax);
	return ret;
}

signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		add_edge(x,y);
		add_edge(y,x);
	}
	for(int i=1;i<=n;i++)cin>>w[i],st.insert(w[i]);
	dfs1(1,0);
	dfs2(1,1);
	tree.build(1,1,n);
	int T;cin>>T;
	while(T--){
		int opt,x,y;
		cin>>opt>>x>>y;
		if(opt==0){
			st.erase(st.find(w[x]));
			st.insert(w[x]+y);
			w[x]+=y;
			tree.modify(1,1,n,dfn[x],y);
		}
		if(opt==1){
			node tmp=Qnode(x,y);
			if(tmp.ttmax==0){
				cout<<-1<<"\n";
				continue;
			}
			st.erase(st.find(tmp.tmax));st.erase(st.find(tmp.ttmax));
			cout<<tmp.ttmax<<" "<<*(--st.lower_bound(*--st.end()))<<"\n";
			st.insert(tmp.tmax);st.insert(tmp.ttmax);
		}
	}
	
	return 0;
}