HLD

///http://lightoj.com/volume_showproblem.php?problem=1348
#include<bits/stdc++.h>

using namespace std;

#define ll long long int
#define db(x) cout<<#x<<" -> "<<x<<endl
#define maxn 30005
#define xx first
#define yy second
#define mp make_pair

typedef pair< int , int > pii;

int sub[maxn],d[maxn],par[maxn];
bool vis[maxn];
int P[maxn][17];
vector< int > g[maxn];
int st[maxn*6],qt[maxn*6];
int chainHead[maxn];
int chainInd[maxn],posInBase[maxn],baseArray[maxn];
int Cost[maxn],otherEnd[maxn];
int n,chainNo=0,ptr=0;
int root ;

void clr(){
    memset(vis,false,sizeof(vis));
    memset(chainHead,-1,sizeof(chainHead));
    chainNo = 0;
    ptr  = 0;
    root = 0;
    for(int i=0; i<=n+5; i++){
        g[i].clear();
    }
}

void dfs(int src, int parent, int dep){
    par[src] =  parent;
    vis[src] =  true;
    d[src]   =  dep;
    sub[src] =  1;
    for(int i=0; i<g[src].size(); i++){
        int temp = g[src][i];
        if( vis[temp] )  continue;
//        otherEnd[index[src][i]] = temp;
        dfs(temp,src,dep+1);
        sub[src]+=sub[temp];
    }
}

int lca_query(int p, int q){
    if( d[p] < d[q] ) swap(p,q);
    int log = 1;
    while(true){
        int next = log+1;
        if((1<<next)>d[p]) break;
        log++;
    }
    for(int i=log; i>=0; i--){
        if((d[p]-(1<<i))>=d[q]){
            p = P[p][i];
        }
    }
    if(p==q) return p;
    for(int i=log; i>=0; i--){
        if(P[p][i]!=-1 && P[p][i]!=P[q][i]){
            p = P[p][i] ; q = P[q][i];
        }
    }
    return par[p];
}

void lca_init(){
    memset(P,-1,sizeof(P));
    for(int i=0; i<n; i++){
        P[i][0] = par[i];
    }
    for(int j=1; (1<<j)<n; j++){
        for(int i=0; i<n; i++){
            if( P[i][j-1]== -1 ) continue;
            P[i][j] = P[P[i][j-1]][j-1];
        }
    }
}

void HLD(int curNode, int cost , int prev){
    if(chainHead[chainNo]==-1){
        chainHead[chainNo] = curNode;
    }
    chainInd[curNode] = chainNo;
    posInBase[curNode] = ptr;
    baseArray[ptr++] = cost;
    int sc = -1;
    int ncost;
    ///Loop to find special child
    for(int i=0; i<g[curNode].size(); i++){
        int temp = g[curNode][i];
        if(temp == prev) continue;
        if(sc==-1 || sub[sc]<sub[temp]){
            sc = temp;
            ncost = Cost[g[curNode][i]];
        }
    }
    if(sc!=-1){
        ///Expand the chain;
        HLD(sc,ncost,curNode);
    }
    for(int i=0; i<g[curNode].size(); i++){
        int temp = g[curNode][i];
        if(temp == prev) continue;
        if(sc!=temp){
            ///New chain at each normal node;
            chainNo++;
            HLD(temp,Cost[temp],curNode);
        }
    }
}

///make segment tree it uses the baseArray for building segment tree
void make_tree(int cur, int s, int e){
    if(s==e-1){
        st[cur] = baseArray[s];
        return ;
    }
    int c1 = (cur<<1) , c2 = c1|1 , m = (s+e)>>1;
    /// in [s,e) range so (s,m) & (m,e) in make_tree
    make_tree(c1,s,m);
    make_tree(c2,m,e);
    st[cur] = st[c1]+st[c2];
}

///point update . Update a single element of the segment tree
void update_tree(int cur, int s, int e, int x, int val){
   // printf("%d %d %d %d %d\n",cur,s,e,x,val);
    if(s>x || e<=x) return ;
    if(s==x && s==e-1){
        st[cur] = val;
//        printf("Cur: %d , val: %d\n",cur,val);
        return;
    }
    int c1 = (cur<<1),c2 = c1|1,m = (s+e)>>1;
    update_tree(c1,s,m,x,val);
    update_tree(c2,m,e,x,val);
    st[cur] = st[c1]+st[c2];
}

///query in the range [s,e)
void query_tree(int cur, int s, int e, int S, int E){
    if(s >= E || e <= S) {
        qt[cur] = 0;
        return;
    }
    if(s >= S && e <= E) {
        qt[cur] = st[cur];
        return;
    }
    int c1 = (cur<<1),c2=c1|1,m = (s+e)>>1;
    query_tree(c1, s, m, S, E);
    query_tree(c2, m, e, S, E);
    qt[cur] = qt[c1]+qt[c2];
}
// * query_up:
// * It takes two nodes u and v, condition is that v is an ancestor of u
// * We query the chain in which u is present till chain head, then move to next chain up
// * We do that way till u and v are in the same chain, we query for that part of chain and break

int query_up(int u, int v){
    if(u==v){ return 0; }
    int uchain,vchain=chainInd[v],ans = 0;
//      uchain & vchain are the chain numbers of u &v respectively!
    while(true){
        uchain = chainInd[u];
//        db(ans);
        if(uchain==vchain){
            if(u==v) break;
//      Both u and v are in the same chain, so we need to query from u to v, update answer and break.
//      We break because we came from u up till v, we are done
           query_tree(1,0,ptr,posInBase[v]+1,posInBase[u]+1);
           ans+=qt[1];
           break;
        }
        query_tree(1,0,ptr,posInBase[chainHead[uchain]],posInBase[u]+1);
//      Above is call to segment tree query function. We do from chainHead of u till u. That is the whole chain from
        ans+=qt[1];
        u = chainHead[uchain];
        u = par[u];
    }
    return ans;
}

int query(int u, int v){
    int lca = lca_query(u,v);
    int x = query_up(u,lca);
    int y = query_up(v,lca);
    return (x+y)+Cost[lca];
}

/*
 * change:
 * We just need to find its position in segment tree and update it
 */

void change(int i, int val){
//    int u = otherEnd[i];
    update_tree(1,0,ptr,posInBase[i],val);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    scanf("%d",&t);
    int tc  = 0;
    memset(chainHead,-1,sizeof(chainHead));
    while(t--){
        scanf("%d",&n);
        for(int i=0; i<n; i++){
            scanf("%d",&Cost[i]);
        }
        for(int i=1; i<=n-1; i++){
            int u,v;
            scanf("%d %d",&u,&v);
            g[u].push_back(v);
            g[v].push_back(u);
//            index[u].push_back(i-1);
//            index[v].push_back(i-1);
        }
        d[0] = 0;
        dfs(0,-1,0);
        lca_init();
        HLD(0,Cost[0],-1);
        make_tree(1,0,ptr);
        printf("Case %d:\n",++tc);
        int q;
        scanf("%d",&q);
        while(q--){
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            if(a==0){
               int ans = query(b,c);
               printf("%d\n",ans);
            }
            else{
                Cost[b] = c;
                change(b,c);
            }
        }
        clr();
    }
    return 0;
}

/**
2
4
10 20 30 40
0 1
1 2
1 3
3
0 2 3
1 1 100
0 2 3
4
10 20 30 40
0 1
1 2
1 3
3
0 2 3
1 1 100
0 2 3
*/