#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#define REP(I,A,B) for(int I=A,_END_=B;I<=_END_;I++)
#define REPD(I,A,B) for(int I=A,_END_=B;I>=_END_;I--)
#define RI(X) X=Readint()
#define RII(X,Y) RI(X),RI(Y)
#define RIII(X,Y,Z) RI(X),RI(Y),RI(Z)
#define RS(X) scanf("%s",X)
#define RD(X) scanf("%lf",&X)
#define GCH getchar()
#define PCH(X) putchar(X)
#define MS(X,Y) memset(X,Y,sizeof(X))
#define MC(X,Y,var,len) memcpy(X,Y,sizeof(var)*(len))
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define pb(X) push_back(X)
#define mp(A,B) make_pair(A,B)
#define fr first
#define sc second
#define lch(p) (p+p)
#define rch(p) (p+p+1)
#define lowbit(X) ((X)&(-(X)))
using namespace std;
typedef pair<int,int> poi;
inline int Readint()
{
int ret=0;
int f=1;
char ch;
do
{
ch=GCH;
if (ch=='-') f*=-1;
}while(ch>=0 && (ch<'0' || ch>'9'));
while ('0'<=ch && ch<='9')
{
ret=ret*10+ch-'0';
ch=GCH;
}
return ret*f;
}
void open()
{
freopen("GSS7.in","r",stdin);
freopen("GSS7.out","w",stdout);
}
void close()
{
fclose(stdin);
fclose(stdout);
}
const int MAXN = 101010;
const int inf = 11111;
int tot;
int to[MAXN*2]={0};
int nxt[MAXN*2]={0};
int hd[MAXN];
int n;
inline void add(const int &x,const int &y){
tot++;
to[tot]=y;
nxt[tot]=hd[x];
hd[x]=tot;
}
struct lct{
bool rev;
bool rt;
int sz;
int sum,mx,lm,rm,val,ocr;
int c[2];
int fa;
lct(){}
lct(int vl){
c[0]=c[1]=fa=0;
ocr=inf;
rt=true;
rev=false;
sum=mx=lm=rm=vl;
val=vl;
sz=1;
}
}t[MAXN];
inline void occur(const int &p,int c){
t[p].sum=t[p].lm=t[p].rm=t[p].mx=c*t[p].sz;
t[p].ocr=t[p].val=c;
}
/*
inline void update_rev(int p){
if (!p) return ;
swap(t[p].c[0],t[p].c[1]);
swap(t[p].lm,t[p].rm);
t[p].rev^=1;
}
*/
inline void maintain(int p){
t[p].sz=t[t[p].c[0]].sz+t[t[p].c[1]].sz+1;
t[p].mx=max(max(t[t[p].c[0]].rm,0)+t[p].val+max(t[t[p].c[1]].lm,0),max(t[t[p].c[0]].mx,t[t[p].c[1]].mx));
t[p].sum=t[t[p].c[0]].sum+t[t[p].c[1]].sum+t[p].val;
t[p].lm=max(t[t[p].c[0]].lm,t[t[p].c[0]].sum+t[p].val+max(t[t[p].c[1]].lm,0));
t[p].rm=max(max(t[t[p].c[0]].rm,0)+t[p].val+t[t[p].c[1]].sum,t[t[p].c[1]].rm);
}
inline void pushdown(int p){
if (t[p].rev)
{
swap(t[p].c[0],t[p].c[1]);
swap(t[p].lm,t[p].rm);
if (t[p].c[0]) t[t[p].c[0]].rev^=1;
if (t[p].c[1]) t[t[p].c[1]].rev^=1;
//update_rev(t[p].c[0]);
//update_rev(t[p].c[1]);
t[p].rev=false;
}
if (t[p].ocr!=inf)
{
if (t[p].c[0])
occur(t[p].c[0],t[p].ocr);
if (t[p].c[1])
occur(t[p].c[1],t[p].ocr);
t[p].ocr=inf;
}
}
inline void setc(const int &p,const int &x,const int &kd){
if (p) t[p].c[kd]=x;
if (x) t[x].fa=p;
}
void rotate(int x){
if (!t[x].fa) return ;
int p=t[x].fa;
pushdown(p);
pushdown(x);
int mark=t[p].c[1]==x;
if (t[p].rt)
{
t[p].rt=false;
t[x].rt=true;
t[x].fa=t[p].fa;
}
else
setc(t[p].fa,x,t[t[p].fa].c[1]==p);
setc(p,t[x].c[mark^1],mark);
setc(x,p,mark^1);
maintain(p);
maintain(x);
}
void splay(int x){
pushdown(x);
while (!t[x].rt)
{
if (t[t[x].fa].rt)
{
rotate(x);
break;
}
if ((t[t[t[x].fa].fa].c[0]==t[x].fa)==(t[t[x].fa].c[0]==x))
rotate(t[x].fa);
else
rotate(x);
rotate(x);
}
}
int expose(int x){
int y=0;
do
{
splay(x);
t[t[x].c[1]].rt=true;
t[x].c[1]=y;
t[y].rt=false;
maintain(x);
x=t[y=x].fa;
}while(x);
return y;
}
int mroot(int x){
expose(x);
splay(x);
t[x].rev^=1;
//update_rev(x);
}
void init()
{
RI(n);
int x,y;
REP(i,1,n) RI(x),t[i]=lct(x);
REP(i,2,n) RII(x,y),add(x,y),add(y,x);
}
void dfs(int p,int fa=0){
for (int i=hd[p];i;i=nxt[i])
if (to[i]!=fa)
{
t[to[i]].fa=p;
dfs(to[i],p);
}
}
void work(){
int _=0;
RI(_);
int op;
int a,b,c;
int now;
REP(__,1,_)
{
RI(op);
RII(a,b);
mroot(a);
now=expose(b);
if (op&1)
printf("%d\n",max(t[now].mx,0));
else
{
RI(c);
occur(now,c);
}
}
}
int main()
{
//open();
int _=0;
init();
dfs(1);
work();
close();
return 0;
}
I2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPGNzdGRsaWI+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPGNzdHJpbmc+CiNpbmNsdWRlIDxjbWF0aD4KI2luY2x1ZGUgPGN0aW1lPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDx2ZWN0b3I+CgojZGVmaW5lIFJFUChJLEEsQikgZm9yKGludCBJPUEsX0VORF89QjtJPD1fRU5EXztJKyspCiNkZWZpbmUgUkVQRChJLEEsQikgZm9yKGludCBJPUEsX0VORF89QjtJPj1fRU5EXztJLS0pCiNkZWZpbmUgUkkoWCkgWD1SZWFkaW50KCkKI2RlZmluZSBSSUkoWCxZKSBSSShYKSxSSShZKQojZGVmaW5lIFJJSUkoWCxZLFopIFJJKFgpLFJJKFkpLFJJKFopCiNkZWZpbmUgUlMoWCkgc2NhbmYoIiVzIixYKQojZGVmaW5lIFJEKFgpIHNjYW5mKCIlbGYiLCZYKQojZGVmaW5lIEdDSCBnZXRjaGFyKCkKI2RlZmluZSBQQ0goWCkgcHV0Y2hhcihYKQojZGVmaW5lIE1TKFgsWSkgbWVtc2V0KFgsWSxzaXplb2YoWCkpCiNkZWZpbmUgTUMoWCxZLHZhcixsZW4pIG1lbWNweShYLFksc2l6ZW9mKHZhcikqKGxlbikpCiNkZWZpbmUgZGVidWcoLi4uKSBmcHJpbnRmKHN0ZGVycixfX1ZBX0FSR1NfXykKI2RlZmluZSBwYihYKSBwdXNoX2JhY2soWCkKI2RlZmluZSBtcChBLEIpIG1ha2VfcGFpcihBLEIpCiNkZWZpbmUgZnIgZmlyc3QKI2RlZmluZSBzYyBzZWNvbmQKI2RlZmluZSBsY2gocCkgKHArcCkKI2RlZmluZSByY2gocCkgKHArcCsxKQojZGVmaW5lIGxvd2JpdChYKSAoKFgpJigtKFgpKSkKCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIHBhaXI8aW50LGludD4gcG9pOwoKaW5saW5lIGludCBSZWFkaW50KCkKewoJaW50IHJldD0wOwoJaW50IGY9MTsKCWNoYXIgY2g7CglkbwoJewoJCWNoPUdDSDsKCQlpZiAoY2g9PSctJykgZio9LTE7Cgl9d2hpbGUoY2g+PTAgJiYgKGNoPCcwJyB8fCBjaD4nOScpKTsKCQoJd2hpbGUgKCcwJzw9Y2ggJiYgY2g8PSc5JykKCXsKCQlyZXQ9cmV0KjEwK2NoLScwJzsKCQljaD1HQ0g7Cgl9CglyZXR1cm4gcmV0KmY7Cn0KCnZvaWQgb3BlbigpCnsKCWZyZW9wZW4oIkdTUzcuaW4iLCJyIixzdGRpbik7CglmcmVvcGVuKCJHU1M3Lm91dCIsInciLHN0ZG91dCk7Cn0Kdm9pZCBjbG9zZSgpCnsKCWZjbG9zZShzdGRpbik7CglmY2xvc2Uoc3Rkb3V0KTsKfQoKY29uc3QgaW50IE1BWE4gPSAxMDEwMTA7CmNvbnN0IGludCBpbmYgPSAxMTExMTsKCmludCB0b3Q7CmludCB0b1tNQVhOKjJdPXswfTsKaW50IG54dFtNQVhOKjJdPXswfTsKaW50IGhkW01BWE5dOwoKaW50IG47CgppbmxpbmUgdm9pZCBhZGQoY29uc3QgaW50ICZ4LGNvbnN0IGludCAmeSl7Cgl0b3QrKzsKCXRvW3RvdF09eTsKCW54dFt0b3RdPWhkW3hdOwoJaGRbeF09dG90Owp9CgpzdHJ1Y3QgbGN0ewoJYm9vbCByZXY7Cglib29sIHJ0OwoJaW50IHN6OwoJaW50IHN1bSxteCxsbSxybSx2YWwsb2NyOwoJaW50IGNbMl07CglpbnQgZmE7CglsY3QoKXt9CglsY3QoaW50IHZsKXsKCQljWzBdPWNbMV09ZmE9MDsKCQlvY3I9aW5mOwoJCXJ0PXRydWU7CgkJcmV2PWZhbHNlOwoJCXN1bT1teD1sbT1ybT12bDsKCQl2YWw9dmw7CgkJc3o9MTsKCX0KfXRbTUFYTl07CgppbmxpbmUgdm9pZCBvY2N1cihjb25zdCBpbnQgJnAsaW50IGMpewoJdFtwXS5zdW09dFtwXS5sbT10W3BdLnJtPXRbcF0ubXg9Yyp0W3BdLnN6OwoJdFtwXS5vY3I9dFtwXS52YWw9YzsKfQovKgppbmxpbmUgdm9pZCB1cGRhdGVfcmV2KGludCBwKXsKCWlmICghcCkgcmV0dXJuIDsKCXN3YXAodFtwXS5jWzBdLHRbcF0uY1sxXSk7Cglzd2FwKHRbcF0ubG0sdFtwXS5ybSk7Cgl0W3BdLnJldl49MTsKfQoqLwoKaW5saW5lIHZvaWQgbWFpbnRhaW4oaW50IHApewoJdFtwXS5zej10W3RbcF0uY1swXV0uc3ordFt0W3BdLmNbMV1dLnN6KzE7Cgl0W3BdLm14PW1heChtYXgodFt0W3BdLmNbMF1dLnJtLDApK3RbcF0udmFsK21heCh0W3RbcF0uY1sxXV0ubG0sMCksbWF4KHRbdFtwXS5jWzBdXS5teCx0W3RbcF0uY1sxXV0ubXgpKTsKCXRbcF0uc3VtPXRbdFtwXS5jWzBdXS5zdW0rdFt0W3BdLmNbMV1dLnN1bSt0W3BdLnZhbDsKCXRbcF0ubG09bWF4KHRbdFtwXS5jWzBdXS5sbSx0W3RbcF0uY1swXV0uc3VtK3RbcF0udmFsK21heCh0W3RbcF0uY1sxXV0ubG0sMCkpOwoJdFtwXS5ybT1tYXgobWF4KHRbdFtwXS5jWzBdXS5ybSwwKSt0W3BdLnZhbCt0W3RbcF0uY1sxXV0uc3VtLHRbdFtwXS5jWzFdXS5ybSk7Cn0KCmlubGluZSB2b2lkIHB1c2hkb3duKGludCBwKXsKCWlmICh0W3BdLnJldikKCXsKCQlzd2FwKHRbcF0uY1swXSx0W3BdLmNbMV0pOwoJCXN3YXAodFtwXS5sbSx0W3BdLnJtKTsKCQlpZiAodFtwXS5jWzBdKSB0W3RbcF0uY1swXV0ucmV2Xj0xOwoJCWlmICh0W3BdLmNbMV0pIHRbdFtwXS5jWzFdXS5yZXZePTE7CgkJLy91cGRhdGVfcmV2KHRbcF0uY1swXSk7CgkJLy91cGRhdGVfcmV2KHRbcF0uY1sxXSk7CgkJdFtwXS5yZXY9ZmFsc2U7Cgl9CgoJaWYgKHRbcF0ub2NyIT1pbmYpCgl7CgkJaWYgKHRbcF0uY1swXSkKCQkJb2NjdXIodFtwXS5jWzBdLHRbcF0ub2NyKTsKCQlpZiAodFtwXS5jWzFdKQoJCQlvY2N1cih0W3BdLmNbMV0sdFtwXS5vY3IpOwoJCXRbcF0ub2NyPWluZjsKCX0KfQoKaW5saW5lIHZvaWQgc2V0Yyhjb25zdCBpbnQgJnAsY29uc3QgaW50ICZ4LGNvbnN0IGludCAma2QpewoJaWYgKHApIHRbcF0uY1trZF09eDsKCWlmICh4KSB0W3hdLmZhPXA7Cn0KCnZvaWQgcm90YXRlKGludCB4KXsKCWlmICghdFt4XS5mYSkgcmV0dXJuIDsKCWludCBwPXRbeF0uZmE7CglwdXNoZG93bihwKTsKCXB1c2hkb3duKHgpOwoKCWludCBtYXJrPXRbcF0uY1sxXT09eDsKCglpZiAodFtwXS5ydCkKCXsKCQl0W3BdLnJ0PWZhbHNlOwoJCXRbeF0ucnQ9dHJ1ZTsKCQl0W3hdLmZhPXRbcF0uZmE7Cgl9CgllbHNlCgkJc2V0Yyh0W3BdLmZhLHgsdFt0W3BdLmZhXS5jWzFdPT1wKTsKCXNldGMocCx0W3hdLmNbbWFya14xXSxtYXJrKTsKCXNldGMoeCxwLG1hcmteMSk7CgkKCW1haW50YWluKHApOwoJbWFpbnRhaW4oeCk7Cn0KCnZvaWQgc3BsYXkoaW50IHgpewoJcHVzaGRvd24oeCk7Cgl3aGlsZSAoIXRbeF0ucnQpCgl7CgkJaWYgKHRbdFt4XS5mYV0ucnQpCgkJewoJCQlyb3RhdGUoeCk7CgkJCWJyZWFrOwoJCX0KCQlpZiAoKHRbdFt0W3hdLmZhXS5mYV0uY1swXT09dFt4XS5mYSk9PSh0W3RbeF0uZmFdLmNbMF09PXgpKQoJCQlyb3RhdGUodFt4XS5mYSk7CgkJZWxzZQoJCQlyb3RhdGUoeCk7CgkJcm90YXRlKHgpOwoJfQp9CgppbnQgZXhwb3NlKGludCB4KXsKCWludCB5PTA7CglkbwoJewoJCXNwbGF5KHgpOwoJCXRbdFt4XS5jWzFdXS5ydD10cnVlOwoJCXRbeF0uY1sxXT15OwoJCXRbeV0ucnQ9ZmFsc2U7CgkJbWFpbnRhaW4oeCk7CgkJeD10W3k9eF0uZmE7Cgl9d2hpbGUoeCk7CglyZXR1cm4geTsKfQoKaW50IG1yb290KGludCB4KXsKCWV4cG9zZSh4KTsKCXNwbGF5KHgpOwoJdFt4XS5yZXZePTE7CgkvL3VwZGF0ZV9yZXYoeCk7Cn0KCnZvaWQgaW5pdCgpCnsKCVJJKG4pOwoJaW50IHgseTsKCVJFUChpLDEsbikgUkkoeCksdFtpXT1sY3QoeCk7CglSRVAoaSwyLG4pIFJJSSh4LHkpLGFkZCh4LHkpLGFkZCh5LHgpOwp9Cgp2b2lkIGRmcyhpbnQgcCxpbnQgZmE9MCl7Cglmb3IgKGludCBpPWhkW3BdO2k7aT1ueHRbaV0pCglpZiAodG9baV0hPWZhKQoJewoJCXRbdG9baV1dLmZhPXA7CgkJZGZzKHRvW2ldLHApOwoJfQp9Cgp2b2lkIHdvcmsoKXsKCWludCBfPTA7CglSSShfKTsKCWludCBvcDsKCWludCBhLGIsYzsKCWludCBub3c7CglSRVAoX18sMSxfKQoJewoJCVJJKG9wKTsKCQlSSUkoYSxiKTsKCQltcm9vdChhKTsKCQlub3c9ZXhwb3NlKGIpOwoJCWlmIChvcCYxKQoJCQlwcmludGYoIiVkXG4iLG1heCh0W25vd10ubXgsMCkpOwoJCWVsc2UKCQl7CgkJCVJJKGMpOwoJCQlvY2N1cihub3csYyk7CgkJfQoJfQp9CgppbnQgbWFpbigpCnsKCS8vb3BlbigpOwoJaW50IF89MDsKCWluaXQoKTsKCWRmcygxKTsKCXdvcmsoKTsKCWNsb3NlKCk7CglyZXR1cm4gMDsKfQoK