e.cpp

#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long

#define IOS ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

using namespace std;
const int MAXN = 1e6 + 10;
const int L = 20;
const int INF = 1e9 + 7;
const int EPS = 1e-6;
int timer = 0;

vector <int> g[MAXN];
pair <string, pair <int, int> > b[MAXN];
int tin[MAXN], tout[MAXN], a[MAXN];
bool was[MAXN];
int up[MAXN][21];
bool upper(int u, int v){
    return (tin[u] <= tin[v] && tout[v] <= tout[u]);
}

void dfs(int v, int pr = 0){
    was[v] = 1;
    tin[v] = ++timer;
    up[v][0] = pr;
    for (int i = 1; i <= L; i++){
        up[v][i] = up[up[v][i - 1]][i - 1];
    }

    for (int to : g[v]){
        if (!was[to]){
            dfs(to, v);
        }
    }
    tout[v] = ++timer;
}

int lca(int a, int b){
    if (upper(a, b)){
        return a;
    }
    if (upper(b, a)){
        return b;
    }
    for (int i = L; i >= 0; i--){
        if (!upper(up[a][i], b)){
            a = up[a][i];
        }
    }

    return up[a][0];
}
int t[4 * MAXN];

int get_sum(int v, int tl, int tr, int l, int r){
    if (l > r){
        return 0;
    }
    if (tl == l && tr == r){
        return t[v];
    }
    int tm = (tl + tr) >> 1;
    return get_sum(v + v, tl, tm, l, min(r, tm)) +
            get_sum(v + v + 1, tm + 1, tr, max(l, tm + 1), r);
}

void update(int v, int tl, int tr, int pos, int val){
    if (tl > tr){
        return;
    }
    if (tl == tr){
        t[v] = val;
        return;
    }
    int tm = (tl + tr) >> 1;
    if (pos <= tm){
        update(v + v, tl, tm, pos, val);
    }
    else{
        update(v + v + 1, tm + 1, tr, pos, val);
    }
    t[v] = t[v + v] + t[v + v + 1];
}

void solve(){
    tin[0] = -INF;
    tout[0] = INF;

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];

    }
    for (int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    dfs(1);
    for (int i = 1; i <= n; i++){
        update(1, 1, n + n, tin[i], a[i]);
        update(1, 1, n + n, tout[i], -a[i]);
    }

    int q;
    cin >> q;
    for (int i = 1; i <= q; i++){
        int type;
        cin >> type;
        if (type == 0){
            int u, v;
            cin >> u >> v;
            int v_lca = lca(u, v);
            cout << get_sum(1, 1, n + n, tin[v_lca], tin[u]) +
                    get_sum(1, 1, n + n, tin[v_lca], tin[v]) - a[v_lca] << "\n";

        }
        else{
            int u, cnt;
            cin >> u >> cnt;
            update(1, 1, n + n, tin[u], cnt);
            update(1, 1, n + n, tout[u], -cnt);
            a[u] = cnt;
        }
    }
}

int main() {
    IOS;
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}