1 #include <map>  2 #include <set>  3 #include <stack>  4 #include <queue>  5 #include <cmath>  6 #include <ctime>  7 #include <string>  8 #include <vector>  9 #include <cstdio> 10 #include <cstdlib> 11 #include <cstring> 12 #include <cassert> 13 #include <iostream> 14 #include <algorithm> 15 #pragma comment(linker,"/STACK:102400000,102400000") 16 using namespace std; 17  18 #define N 300008              19 #define M 50008     20 #define LL long long 21 #define lson l,m,rt<<1 22 #define rson m+1,r,rt<<1|1  23 #define clr(x,v) memset(x,v,sizeof(x)); 24 #define bitcnt(x) __builtin_popcount(x) 25 #define rep(x,y,z) for (int x=y;x<=z;x++) 26 #define repd(x,y,z) for (int x=y;x>=z;x--) 27 const int mo  = 1000000007; 28 const int inf = 0x3f3f3f3f; 29 const int INF = 2000000000; 30 /**************************************************************************/ 31  32 int val[N],c[N][2],fa[N],mx[N],tag[N],rev[N],lt[N],st[N]; 33 int n,q,sum; 34 struct line{ 35     int u,v,nt; 36 }eg[N*2]; 37 void addedge(int u,int v){ 38     eg[++sum]=(line){u,v,lt[u]}; 39     lt[u]=sum; 40 } 41 void init(){ 42     rep(i,1,n) val[i]=c[i][0]=c[i][1]=mx[i]=tag[i]=rev[i]=lt[i]=fa[i]=0; 43     sum=1; 44 } 45 void dfs(int u){ 46     for (int i=lt[u];i;i=eg[i].nt){ 47         int v=eg[i].v; 48         if (fa[v] || v==1) continue; 49         fa[v]=u; 50         dfs(v); 51     } 52 } 53 bool isroot(int k){ 54     return c[fa[k]][0]!=k && c[fa[k]][1]!=k; 55 } 56 void pushup(int x){ 57     int l=c[x][0],r=c[x][1]; 58     mx[x]=max(max(mx[l],mx[r]),val[x]); 59 } 60 void pushdown(int x){ 61     int l=c[x][0],r=c[x][1]; 62     if (rev[x]){ 63         if (l) rev[l]^=1; 64         if (r) rev[r]^=1; 65         rev[x]^=1; 66         swap(c[x][0],c[x][1]); 67     } 68     if (tag[x]){ 69         if (l) {tag[l]+=tag[x]; mx[l]+=tag[x], val[l]+=tag[x]; } 70         if (r) {tag[r]+=tag[x]; mx[r]+=tag[x], val[r]+=tag[x]; } 71         tag[x]=0; 72     } 73 } 74 void rotate(int x){ 75     int y=fa[x],z=fa[y],l,r; 76     if (c[y][0]==x) l=0; else l=1; r=l^1; 77     if (!isroot(y)){ 78         if (c[z][0]==y) c[z][0]=x; else c[z][1]=x; 79     } 80     fa[x]=z; fa[y]=x; fa[c[x][r]]=y; 81     c[y][l]=c[x][r]; c[x][r]=y; 82     pushup(y); pushup(x); 83 } 84 void splay(int x){ 85     int top=0; st[++top]=x; 86     for (int i=x;!isroot(i);i=fa[i]) st[++top]=fa[i]; 87     while (top) pushdown(st[top--]); 88     while (!isroot(x)){ 89         int y=fa[x],z=fa[y]; 90         if (!isroot(y)){ 91             if (c[y][0]==x^c[z][0]==y) rotate(x); 92             else rotate(y); 93         } 94         rotate(x); 95     } 96 } 97 void access(int x){ 98     int t=0; 99     while (x){100         splay(x);101         c[x][1]=t;102         pushup(x);            103         t=x; x=fa[x];104     }105 }106 int find(int u){107     access(u); splay(u);108     while (c[u][0]) u=c[u][0];109     return u;110 }111 bool judge(int u,int v){112     return find(u)==find(v);113 }114 void rever(int u){115     access(u); splay(u); rev[u]^=1;116 }117 void link(int u,int v){118     rever(u); fa[u]=v; 119 }120 void cut(int u,int v){121     rever(u); access(v); splay(v); fa[c[v][0]]=0; c[v][0]=0; pushup(v);122 }123 void add(int u,int v,int w){124     rever(u); access(v); splay(v); tag[v]+=w; mx[v]+=w; val[v]+=w;125 }126 void query(int u,int v){127     rever(u); access(v); splay(v); printf("%d\n",mx[v]);128 }129 int main(){130     while (~scanf("%d",&n))131     {132         init();133         rep(i,1,n-1){134             int u,v;135             scanf("%d%d",&u,&v);136             addedge(u,v); addedge(v,u);137         }138         rep(i,1,n){139             int x;140             scanf("%d",&x);141             val[i]=mx[i]=x;142         }143         dfs(1);144         scanf("%d",&q);145         while (q--){146             int x,u,v,w;147             scanf("%d",&x);148             if (x==1){149                 scanf("%d %d",&u,&v);        150                 if (!judge(u,v)) link(u,v); else puts("-1");151             }152             if (x==2){153                 scanf("%d %d",&u,&v);        154                 if (judge(u,v) && u!=v) cut(u,v); else puts("-1");155             }156             if (x==3){157                 scanf("%d %d %d",&w,&u,&v);158                 if (judge(u,v)) add(u,v,w);    else puts("-1");159             }160             if (x==4){161                 scanf("%d %d",&u,&v);        162                 if (judge(u,v)) query(u,v); else puts("-1");163             }164         }165         printf("\n");166     }167 }