HLD

#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define ff first
#define ss second
#define mx 40100
int base[mx],tree[6*mx],level[mx],parent[mx],SubtrSiz[mx],arr[mx];vector<int>adj[mx];

int chainLeader[mx],chain[mx],basepos[mx],ptr=1,ch;


void Build(int node,int b,int e)
{
    if(b==e)
    {
        tree[node]=base[b];
        return;
    }
    int mid=(b+e)/2;
    int left=2*node;
    int right=left+1;
    Build(left,b,mid);
    Build(right,mid+1,e);
    tree[node]=tree[left]+tree[right];
}

int query(int node,int b,int e,int l,int r)
{
    if(b>r||l>e)return 0;

    if(b>=l&&e<=r)return tree[node];

    int mid=(b+e)/2;
    int left=2*node;
    int right=left+1;

    int p1=query(left,b,mid,l,r);
    int p2=query(right,mid+1,e,l,r);

    return p1+p2;
}

void update(int node,int b,int e,int newVal,int pos)
{
    if(b>pos||e<pos)return;
    if(b==e)
    {
        base[b]=newVal;
        tree[node]=base[b];
        return;
    }
    int mid=(b+e)/2;
    int left=2*node;
    int right=left+1;
    update(left,b,mid,newVal,pos);
    update(right,mid+1,e,newVal,pos);
    tree[node]=tree[left]+tree[right];
}

int dfs(int s,int lev,int pr)
{
    level[s]=lev;
    parent[s]=pr;
    SubtrSiz[s]=1;
    for(int i=0;i<adj[s].size();i++)
    {
        int u=adj[s][i];
        if(u!=parent[s])
        {
            SubtrSiz[s]+=dfs(u,lev+1,s);
        }
    }
    return SubtrSiz[s];
}


void HLD(int node,int chainNo,int cst,bool isL)
{
    if(isL)
    {
        chainNo=++ch;
        chainLeader[chainNo]=node;
    }

    chain[node]=chainNo;
    basepos[node]=ptr;
    base[ptr++]=cst;

    int Heavy=-1,Heavynode,Heavycost;
    for(int i=0;i<adj[node].size();i++)
    {
        int u=adj[node][i];
        if(u==parent[node])continue;
        if(SubtrSiz[u]>Heavy)
        {
            Heavy=SubtrSiz[u];
            Heavynode=u;
            Heavycost=arr[u];
        }
    }

    if(Heavy==-1)return;
    HLD(Heavynode,chainNo,Heavycost,false);

    for(int i=0;i<adj[node].size();i++)
    {
        int u=adj[node][i];
        int w=arr[u];
        if(u==parent[node]||u==Heavynode)continue;
        HLD(u,0,w,true);
    }
}

int lca(int u,int v)
{
    while(chain[u]!=chain[v])
    {
        if(level[chainLeader[chain[u]]]>level[chainLeader[chain[v]]])
        {
            u=parent[chainLeader[chain[u]]];
        }
        else
            v=parent[chainLeader[chain[v]]];
    }

    if(level[u]<level[v])return u;
    else return v;
}


int query_up(int u,int v)
{
    int maxi=0;
    while(1)
    {
        //cout<<basepos[u]<<" "<<basepos[v]<<" "<<u<<" "<<v<<endl;
        if(chain[u]==chain[v])
        {
            int x=query(1,1,ptr,min(basepos[u],basepos[v]),max(basepos[u],basepos[v]));
            maxi+=x;
            break;
        }
        int y=query(1,1,ptr,min(basepos[u],basepos[chainLeader[chain[u]]]),max(basepos[u],basepos[chainLeader[chain[u]]]));
        maxi+=y;
        u=parent[chainLeader[chain[u]]];
    }

    return maxi;
}

int giveres(int node1,int node2)
{
    int LCA=lca(node1,node2);
    //cout<<LCA<<endl;
    int max1=query_up(node1,LCA);
    int max2=query_up(node2,LCA);
    return max1+max2-base[basepos[LCA]];
}

int main()
{

    int t;
    scanf("%d",&t);
    for(int q=0;q<t;q++)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",&arr[i]);
        int root=1;
        for(int i=0;i<=n;i++)
        {
            adj[i].clear();
        }
        ptr=1;ch=0;
        for(int i=0;i<n-1;i++)
        {
            int a,b,c;
            scanf("%d%d",&a,&b);
            a++;b++;
            adj[a].push_back(b);
            adj[b].push_back(a);
            root=1;
        }

        dfs(root,1,root);
        HLD(root,0,arr[1],true);
        ptr--;
        Build(1,1,ptr);
        int qt;
        scanf("%d",&qt);
        printf("Case %d:\n",q+1);
        for(int i=0;i<qt;i++)
        {
            int cho;
            scanf("%d",&cho);
            if(cho==0)
            {
                int node1,node2;
                scanf("%d%d",&node1,&node2);
                node1++;node2++;
               // for(int i=1;i<=ptr;i++)cout<<base[i]<<" ";cout<<endl;
                //cout<<query(1,1,ptr,3,6)<<endl;
                printf("%d\n",giveres(node1,node2));
            }
            else
            {
                int ed,val;
                scanf("%d%d",&ed,&val);
                ed++;
                arr[ed]=val;
                update(1,1,ptr,val,basepos[ed]);
            }
        }

    }


}