#include<cstdio>
#include<vector>
using namespace std;
const int maxn = 100004;
int n,m,tq = 1,cv;
int va[maxn],tree[maxn],fa[maxn],son[maxn],size[maxn],deep[maxn],w[maxn],top[maxn];//va为每个公园的权值
class node{
public:
int xds,maxl,maxr,sum,set;
}tre[4*maxn];
vector<int> rd[maxn];
inline int max(int a,int b,int c)//求3数最大值
{
if(a<b)
a = b;
if(a<c)
a = c;
return a;
}
inline void combine(node &t,node &l,node &r)//将两个区间合并 结果存在t中
{
t.xds = max(l.xds,r.xds,l.maxr+r.maxl);
t.maxl = max(l.maxl,l.sum+r.maxl);
t.maxr = max(r.maxr,r.sum+l.maxr);
t.sum = r.sum+l.sum;
}
void down(int x,int lenth)
{
if(tre[x].set!=10001)
{
tre[x].sum = tre[x].set*(lenth);
tre[x].maxl=tre[x].maxr=tre[x].xds= tre[x].set>0 ? tre[x].sum : tre[x].set;
if(lenth!=1)
tre[x*2].set=tre[x*2+1].set=tre[x].set;
tre[x].set=10001;
}
}
void bdtree(int x)//第一遍dfs 求出深度 父亲节点 重儿子节点 和 size
{
//每次更新到一个节点时已经计算出来了父亲节点和深度，size则是由递归回溯时计算 重儿子如果叶节点则为0（因为节点编号1-n）
size[x]=1;
int maxs = 0;
for(int i = 0;i<rd[x].size();i++)
{
if(rd[x][i]!=fa[x])
{
fa[rd[x][i]]=x;
deep[rd[x][i]]=deep[x]+1;
bdtree(rd[x][i]);
size[x]+=size[rd[x][i]];
if(maxs<size[rd[x][i]])//找重儿子
{
maxs=size[rd[x][i]];
son[x]=rd[x][i];
}
}
}
}
void btree(int x)//第二遍dfs 将重边联成链加入线段树 计算top数组
{
w[x]=tq;//每到一个节点 top必定已出 将其权值加入线段树
tree[tq++]=va[x];
if(son[x]==0)//如果是叶子节点就没有其他的事了
return;
top[son[x]]=top[x];
btree(son[x]);//先往重边dfs
for(int i = 0;i<rd[x].size();i++)
{
if(rd[x][i]!=fa[x]&&rd[x][i]!=son[x])//对所有轻儿子 在重链递归结束后再分别dfs
{
top[rd[x][i]]=rd[x][i];//由于是轻儿子 肯定是自己链的顶端
btree(rd[x][i]);
}
}
}
void xdtree(int x,int l,int r)//建线段树
{
tre[x].set=10001;//10001代表没有修改
if(l==r)//叶子节点
{
if(tree[l]<=0)
tre[x].maxr = tre[x].maxl = tre[x].xds = 0;
else
tre[x].maxr = tre[x].maxl = tre[x].xds = tree[l];
tre[x].sum = tree[l];
return;
}
int md = (l+r)>>1;
xdtree(x*2,l,md);
xdtree(x*2+1,md+1,r);
combine(tre[x],tre[x*2],tre[x*2+1]);
return;
}
void tchange(int x,int l,int r,int nl,int nr)//修改的重点
{
if(l==nl&&r==nr)//完全覆盖的话就直接把set改掉然后更新
{
tre[x].set=cv;
down(x,nr-nl+1);
return;
}
down(x,nr-nl+1);
int md = (nl+nr)>>1;
if(r<=md)//如果只改左节点 那么右节点手动更新
{
tchange(x*2,l,r,nl,md);
down(x*2+1,nr-md);
}else if(l>md)//同理
{
tchange(x*2+1,l,r,md+1,nr);
down(x*2,md-nl+1);
}else //均改的话则递归过程中自己会更新
{
tchange(x*2,l,md,nl,md);
tchange(x*2+1,md+1,r,md+1,nr);
}
combine(tre[x],tre[x*2],tre[x*2+1]);//维护自身
}
node tserch(int x,int l,int r,int nl,int nr)//线段树查找部分
{
down(x,nr-nl+1);
if(nl==l&&nr==r)//如果包含该区间
return tre[x];
int md = (nl+nr)>>1;
if(r<=md)
{
return tserch(x*2,l,r,nl,md);
}else if(l>md)
{
return tserch(x*2+1,l,r,md+1,nr);
}else
{
node temps = tserch(x*2,l,md,nl,md);
node tempv = tserch(x*2+1,md+1,r,md+1,nr);
combine(temps,temps,tempv);
return temps;
}
}
int serch(int x,int y)//求路径最大值
{
node temx,temy,tems;
temy.maxl=temy.maxr=temy.sum=temy.xds=temx.maxl=temx.maxr=temx.sum=temx.xds=0;
while(top[x]!=top[y])//如果不在一条重链上
{
//重链低的那个计算出到顶端的数据 然后走到顶端的父亲节点
if(deep[top[x]]>deep[top[y]])
{
//线段树建树时是上面的在前面
tems = tserch(1,w[top[x]],w[x],1,n);//得到的数据是从top到节点方向的信息（即l是top r是节点）
combine(temx,tems,temx);//由于上l下r 所以原来的可以理解成右边区间 左右合并更新temx/y
x = fa[top[x]];//向上走
}else
{
tems = tserch(1,w[top[y]],w[y],1,n);
combine(temy,tems,temy);
y = fa[top[y]];
}
}
//此时两个节点到了一个重链上 其中tem分别保存的是各自当前点到原点的路径信息
if(deep[x]>deep[y])//y在上方
{
tems = tserch(1,w[y],w[x],1,n);
combine(temx,tems,temx);
}else//x在上方或两点重合
{
tems = tserch(1,w[x],w[y],1,n);
combine(temy,tems,temy);
}
//得到两个紧挨着（不相交）的重链信息 由于上l下r 所以相当于两个的l是中间 r是两边
return max(temx.xds,temy.xds,temx.maxl+temy.maxl);
}
void change(int x,int y)//修改和查询的过程差不多 一样是一段一段的修改 只不过不用记录合成 所以简便了许多
{
while(top[x]!=top[y])//如果不在一条重链上
{
//重链低的那个进行修改 然后走到顶端的父亲节点
if(deep[top[x]]>deep[top[y]])
{
tchange(1,w[top[x]],w[x],1,n);
x = fa[top[x]];//向上走
}else
{
tchange(1,w[top[y]],w[y],1,n);
y = fa[top[y]];//向上走
}
}
//此时两个节点到了一个重链上
if(deep[x]>deep[y])//y在上方
tchange(1,w[y],w[x],1,n);
else//x在上方或两点重合
tchange(1,w[x],w[y],1,n);
return;
}
int main()
{
int x,y,k;
scanf("%d",&n);
for(int i = 1;i<=n;i++)
scanf("%d",&va[i]);
for(int i = 1;i<n;i++)
{
scanf("%d%d",&x,&y);
rd[x].push_back(y);
rd[y].push_back(x);
}
deep[1]=1;
top[1]=1;
bdtree(1);
btree(1);
xdtree(1,1,n);
//预处理结束↑
scanf("%d",&m);
int test;
/*for(int i =1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&cv);
change(x,y);
for(int i = 1;i<=n;i++)
{
for(int j = i+1;j<=n;j++)
{
printf("%d ",serch(i,j));
}
printf("\n");
}
}*/
for(int i =1;i<=m;i++)
{
scanf("%d",&k);
if(k==1)
{
scanf("%d%d",&x,&y);
printf("%d ",serch(x,y));
}else
{
scanf("%d%d%d",&x,&y,&cv);
change(x,y);
}
}
printf("\n");
return 0;
}