当你询问一个点 $x$ 的答案时，我们可以忽视 $x$ 贡献到其邻域的过程。也就是说，我们可以以 $x$ 为根，然后只考虑儿子到父亲的贡献。

暴力就是设 $dp_u$ 表示 $u$ 的答案，然后 $dp_u$ 等于所有儿子 $v$ 的 $dp_v+D_{u,v}$ 取第 $C_u$ 小。

考虑加速这个转移，由于转移和儿子强相关，考虑重剖一下，对于轻儿子暴力处理一些东西来加速重儿子转移。

具体而言，我们设 $f_{i}$ 表示以 $1$ 为根时 $i$ 的 $dp_i$。用平衡树维护一个点 $u$ 的所有轻儿子 $v$ 的 $f_v+D_{u,v}$，那么从 $u$ 的重儿子的 $f_{son_u}$ 转移到 $f_u$ 的形式就是 $f_u=\max(l,\min(r,f_{son_u}))$。其中 $l$ 是轻儿子中第 $C_u-1$ 小，$r$ 是轻儿子中第 $C_u$ 小。容易发现这个变换是可以复合的，于是可以用线段树快速维护出来。至此我们可以在 $O((n+q) \log^2 n)$ 的时间复杂度内支持修改以及快速求出所有 $f$ 的值。

当查询 $x$ 的答案是，对于 $x$ 祖先链的部分，倒着跳重链，并用线段树维护在重链上从上往下走复合出来的函数即可，时间复杂度也是 $O((n+q) \log^2 n)$ 的。

#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define int long long
const int maxn = 2e5+114;
const int inf = 1e18;
struct info{
	int l,r,c;
	//先加上 c，然后<l 的变成 l : >r 的变成 r : 其余不变
	info(int C=0,int L=-inf,int R=inf){
		c=C,l=L,r=R;
	}
	info operator+(const info &x){
		//l+=x.c
		//r+=x.c
		//c+=x.c
		if(x.r<=l+x.c) return info(c+x.c,x.r,x.r);
		else if(x.l>=r+x.c) return info(c+x.c,x.l,x.l);
		else return info(c+x.c,max(l+x.c,x.l),min(r+x.c,x.r));
	}	
	int operator*(const int &x){
		return max(l,min(r,x+c));
	}
};
tree< pair<int,int> , null_type, less< pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> Tr[maxn];//维护轻儿子 dp 值
int dfn[maxn];
int node[maxn],dfncnt;
int sz[maxn];
int son[maxn];
info tr[maxn<<2][2];
//从下到上和从上到下
//从下到上：u 上维护 dp 值从 son[u] 转移到 u
//从上到下：u 上维护 dp 值从 fa[u] 转移到 u
int U[maxn],V[maxn],D[maxn];
int C[maxn];
vector< pair<int,int> > E[maxn];
int fa[maxn];
int n,m;
void dfs1(int u){
	sz[u]=1;
	for(pair<int,int> now:E[u]){
		int v=now.first;
		if(v!=fa[u]){
			fa[v]=u;
			dfs1(v);
			if(sz[v]>sz[son[u]]) son[u]=v;
			sz[u]+=sz[v];
		}
	}
}
int top[maxn];
void dfs2(int u,int tp){
	top[u]=tp;
	dfn[u]=++dfncnt;
	node[dfncnt]=u;
	if(son[u]!=0){
		dfs2(son[u],tp);
		for(pair<int,int> now:E[u]){
			int v=now.first;
			if(v!=son[u]&&v!=fa[u]) dfs2(v,v);
		}
	}
}
void pushup(int cur){
	tr[cur][0]=tr[cur<<1|1][0]+tr[cur<<1][0];
	tr[cur][1]=tr[cur<<1][1]+tr[cur<<1|1][1];
}
void upd(int cur,int lt,int rt,int pos,int ty,info c){
	if(lt==rt){
		tr[cur][ty]=c;
		return ;
	}
	int mid=(lt+rt)>>1;
	if(pos<=mid) upd(cur<<1,lt,mid,pos,ty,c);
	else upd(cur<<1|1,mid+1,rt,pos,ty,c);
	pushup(cur);
}
info ask(int cur,int lt,int rt,int l,int r,int ty){
	if(rt<l||r<lt) return info();
	if(l<=lt&&rt<=r) return tr[cur][ty];
	int mid=(lt+rt)>>1;
	if(ty==0) return ask(cur<<1|1,mid+1,rt,l,r,ty)+ask(cur<<1,lt,mid,l,r,ty);
	else return ask(cur<<1,lt,mid,l,r,ty)+ask(cur<<1|1,mid+1,rt,l,r,ty);
}
int dp[maxn];//重链顶部的 dp 值
int dfs3(int u){
	vector<int> vec;
	vec.push_back(0);
	for(pair<int,int> now:E[u]){
		int v=now.first,id=now.second;
		if(v!=fa[u]){
			int res=dfs3(v)+D[id];
			vec.push_back(res);
			if(v!=son[u]) Tr[u].insert({res,v});
		}
	}
	sort(vec.begin(),vec.end());
	if(u!=son[fa[u]]){
		dp[u]=(C[u]<vec.size()?vec[C[u]]:inf);
	}
	return (C[u]<vec.size()?vec[C[u]]:inf);
}
int query1(int u){
	int lt=dfn[u],rt=n+1;
	while(lt+1<rt){
		int mid=(lt+rt)>>1;
		if(top[node[mid]]==top[u]) lt=mid;
		else rt=mid;
	}
	int v=node[lt];
	//v 是重链底
	return ask(1,1,n,dfn[u],dfn[v],0)*inf;
}//只考虑子树内时 u 的 dp 值
const int _0index = -1;
map<int,int> mp[maxn];
int query2(int u,int v){
	if(u==0) return inf;
	if(C[u]==0) return 0;
	int res=(u==top[u]?info():ask(1,1,n,dfn[top[u]],dfn[u]-1,1))*query2(fa[top[u]],top[u]);
	if(v==son[u]){
		return ask(1,1,n,dfn[u],dfn[u],1)*res;
	}else{
		Tr[u].insert({res+mp[fa[u]][u],fa[u]});
		Tr[u].erase({dp[v]+mp[v][u],v});
		int val=query1(son[u])+mp[son[u]][u];
		Tr[u].insert({val,son[u]});
		int ans=(Tr[u].size()>=C[u]?(*Tr[u].find_by_order(_0index+C[u])).first:inf);
		Tr[u].erase({val,son[u]});
		Tr[u].insert({dp[v]+mp[v][u],v});
		Tr[u].erase({res+mp[fa[u]][u],fa[u]});
		return ans;
	}
}//只考虑 v 的子树补时 u 的 dp 值（保证 v 是 u 的一个儿子）
void sol(int u){
	info c=info();
	c.c=mp[u][son[u]];
	//<=rk[C[u]-1] 答案是 rk[C[u]-1]
	//>=rk[C[u]] 答案是 rk[C[u]]
	c.l=(C[u]<=1?-inf:(C[u]-1<=Tr[u].size()?(*Tr[u].find_by_order(_0index+C[u]-1)).first:inf));
	c.r=(C[u]<=0?0:(C[u]<=Tr[u].size()?(*Tr[u].find_by_order(_0index+C[u])).first:inf));
	upd(1,1,n,dfn[u],0,c);
	c.c=mp[u][fa[u]];
	upd(1,1,n,dfn[u],1,c);
}
void jump(int u){
	if(fa[top[u]]!=0){
		Tr[fa[top[u]]].erase({dp[top[u]]+mp[top[u]][fa[top[u]]],top[u]});
	}
	dp[top[u]]=query1(top[u]);
	if(fa[top[u]]!=0){
		Tr[fa[top[u]]].insert({dp[top[u]]+mp[top[u]][fa[top[u]]],top[u]});
		sol(fa[top[u]]);
		jump(fa[top[u]]);
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>U[i]>>V[i]>>D[i];
		E[U[i]].push_back({V[i],i});
		E[V[i]].push_back({U[i],i});
		mp[U[i]][V[i]]=D[i];
		mp[V[i]][U[i]]=D[i];
	}
	for(int i=1;i<=n;i++) cin>>C[i];
	dfs1(1);
	dfs2(1,1);
	dfs3(1);
	for(int u=1;u<=n;u++){
		sol(u);
	}
	cin>>m;
	while(m--){
		int ty;
		cin>>ty;
		if(ty==1){
			int x,y;
			cin>>x>>y;
			C[x]=y;
			sol(x);
			jump(x);
		}else if(ty==2){
			int x,y;
			cin>>x>>y;
			if(fa[U[x]]!=V[x]) swap(U[x],V[x]);
			if(son[V[x]]!=U[x]){
				Tr[V[x]].erase({dp[U[x]]+D[x],U[x]});
			}//修改轻儿子信息
			D[x]=y;
			if(son[V[x]]!=U[x]){
				Tr[V[x]].insert({dp[U[x]]+D[x],U[x]});
			}
			mp[U[x]][V[x]]=D[x];
			mp[V[x]][U[x]]=D[x];
			sol(U[x]);
			sol(V[x]);
			jump(U[x]);
		}else{
			int x;
			cin>>x;
			int v1,v2;
			if(fa[x]!=0){
				v1=query2(fa[x],x)+mp[fa[x]][x];
				Tr[x].insert({v1,fa[x]});
			}
			if(son[x]!=0){
				v2=query1(son[x])+mp[son[x]][x];
				Tr[x].insert({v2,son[x]});
			}
			if(C[x]==0) cout<<0<<"\n";
			else{
				int ans=((Tr[x].size()>=C[x])?(*Tr[x].find_by_order(_0index+C[x])).first:inf);
				cout<<(ans>=inf?-1:ans)<<"\n";
			}
			if(son[x]!=0) Tr[x].erase({v2,son[x]});
			if(fa[x]!=0) Tr[x].erase({v1,fa[x]});
		}
	}
	return 0;
}