题解：P13698 「CyOI」追忆
喜欢分块虚树。
解决路径上点相关问题，可以使用分块+虚树。
之前 P9999 有一个分块虚树做法，大概是每一个块操作的时候遍历当前块的虚树进行暴力操作，附带合并点后每次操作的点数是
这个还带了一个分块求集合值，则直接值域分块，每一块先统计当前整块有多少个点在虚树上，树上差分维护一下散块信息，检测到答案在这个块内的时候跑出答案即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll1;
template<typename T>
void in(T &n){
n=0;char c=getchar();bool flag=0;
for(;c<'0'||c>'9';c=getchar()) if (c=='-') flag=1;
for(;c>='0'&&c<='9';c=getchar()) (n*=10)+=(c^48);
if (flag) n=-n;
}
int wlsk[45];int wltp;
template<typename T>
void out(T n,char c=0){
if (n==0){putchar('0');if (c)putchar(c);return ;}
if (n<0) putchar('-'),n=-n;
while(n) wlsk[++wltp]=(n%10),n/=10;
while(wltp) putchar(wlsk[wltp--]^48);
if (c) putchar(c);
}
const int N=1e5+5;
int a[N],p[N];
vector<int>e[N];
int n,q,B,tb=0;
int fa[N],d[N],Log2[N];
int dfn[N],dfns[18][N],tdfn=0;
int L[N],R[N],bel[N];
int OP[N],X[N],Y[N],CK[N];
ll1 Len[N],NL[N],NL1[N];
ll1 Ans[N];
bool cmp(int x,int y){return a[x]<a[y];}
int cmpr(int x,int y){return d[x]<d[y]?x:y;}
void dfs(int u,int Fa,int D){
d[u]=D,fa[u]=Fa;
dfn[u]=++tdfn,dfns[0][tdfn]=u;
for(auto v:e[u])
if(v!=Fa)dfs(v,u,D+1);
}
int Lca(int x,int y){
if(x==y)return x;
x=dfn[x],y=dfn[y];
if(x>y)swap(x,y);
x++;int k=Log2[y-x+1];
return fa[cmpr(dfns[k][x],dfns[k][y-(1<<k)+1])];
}
int Dis(int x,int y){return d[x]+d[y]-2*d[Lca(x,y)]+1;}
void init(){
in(n);
for(int i=1;i<=n;i++)
in(a[i]),p[i]=i,e[i].clear();
for(int u,v,i=1;i<n;i++){
in(u),in(v);
e[u].emplace_back(v);
e[v].emplace_back(u);
}
sort(p+1,p+1+n,cmp);
dfs(1,0,1);
for(int k=1;k<=Log2[n];k++)
for(int i=1;i+(1<<k)-1<=n;i++)
dfns[k][i]=cmpr(dfns[k-1][i],dfns[k-1][i+(1<<(k-1))]);
in(q);
Len[0]=0;
for(int i=1;i<=q;i++){
Len[i]=Len[i-1];in(OP[i]);
NL[i]=0;
if(OP[i]==1){
in(X[i]),in(Y[i]),in(CK[i]);
Len[i]+=Dis(X[i],Y[i])*CK[i];
}
if(OP[i]==3){
if(Len[i]!=0)Len[i]<<=1;
else OP[i]=4;//无效的
}
Ans[i]=-1;
}
}
bool cmpdfn(int x,int y){return dfn[x]<dfn[y];}
int s[N],ups[N];
bool vis[N];
int tr[N],tot,root;
vector<int>E[N];
ll1 diff[N];//树上差分
ll1 sms[N];
int ff[N];
void solve(int l,int r){
for(int i=0;i<=n;i++)s[i]=0,E[i].clear(),ups[i]=0,vis[i]=0;
for(int i=l;i<=r;i++)s[p[i]]=1,vis[p[i]]=1;
for(int u,i=2;i<=n;i++)u=dfns[0][i],s[u]+=s[fa[u]];
tot=0;for(int i=l;i<=r;i++)tr[++tot]=p[i];
{
sort(tr+1,tr+1+tot,cmpdfn);
for(int i=2,tt=tot;i<=tt;i++)tr[++tot]=Lca(tr[i],tr[i-1]);
sort(tr+1,tr+1+tot,cmpdfn);
tot=unique(tr+1,tr+1+tot)-tr-1;
for(int i=1;i<=tot;i++)ups[tr[i]]=tr[i],diff[tr[i]]=0;
root=tr[1];
for(int u,i=1;i<=n;i++){
u=dfns[0][i];if(!ups[u])ups[u]=ups[fa[u]];
}//虚树上的对应点
for(int i=1;i<=tot;i++)ff[tr[i]]=ups[fa[tr[i]]];
}
NL1[0]=0;
for(int id=1;id<=q;id++){
NL1[id]=NL1[id-1];
if(OP[id]==1){
int u=X[id],v=Y[id],lca=Lca(u,v);
diff[ups[u]]+=CK[id],diff[ups[v]]+=CK[id];
diff[ups[lca]]-=CK[id],diff[ups[fa[lca]]]-=CK[id];
NL1[id]+=CK[id]*(s[u]+s[v]-s[lca]-s[fa[lca]]);
}
if(OP[id]==3){
NL1[id]<<=1;
for(int i=1;i<=tot;i++)diff[tr[i]]<<=1;
}
ll1 MID=(Len[id]+1)>>1;
if(OP[id]==2&&NL[id]<MID&&NL[id]+NL1[id]>=MID){
Ans[id]=-5;
for(int i=1;i<=tot;i++)sms[tr[i]]=diff[tr[i]];
for(int i=tot;i;i--){
int u=tr[i];
sms[ff[u]]+=sms[u];
}
ll1 ts=NL[id];
for(int i=l;i<=r;i++){
ts+=sms[p[i]];
if(ts>=MID){
Ans[id]=a[p[i]];
break;
}
}
}
NL[id]+=NL1[id];
}
}
void work(){
B=sqrt(n*2);
L[tb=0]=-B;
for(int i=1;i<=n;i++){
if(L[tb]+B<=i)L[++tb]=i;
R[tb]=i,bel[i]=tb;
}
for(int o=1;o<=tb;o++){
int l=L[o],r=R[o];
solve(l,r);
}
for(int i=1;i<=q;i++)
if(OP[i]==2)
assert(Ans[i]!=-1);
for(int i=1;i<=q;i++)
if(OP[i]==2)out(Ans[i],'\n');
}
signed main(){
for(int i=2;i<=100000;i++){
Log2[i]=Log2[i-1];
if((1<<(Log2[i]+1))==i)Log2[i]++;
}
init();
work();
return 0;
}