算法竞赛模板

显然树剖，但是操作2暴力维护显然会T，发现一个性质，对于一条重链上，任意一个非链顶节点，其父亲的
重儿子必为该节点。
这启发我们，每次修改就只需要对父亲 Fa𝑥 与重儿子 son𝑥
进行单点修改。所有非链顶节点都可以正确更新，唯独链顶节点
不能正确更新。
不难发现，单点查询可以轻松 𝑂(1) 维护，然后对该位置打上标记。故我们只需要在
路径查询的过程中，对链顶节点额外单点查询即可。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define LOCAL
#ifdef LOCAL
#define dbg(...) _((char*)#__VA_ARGS__,__VA_ARGS__)
template<typename t> void _(char* p,t x){cout<<p<<'='<<x<<'\n';}
template<typename t,typename... a>
void _(char* p,t x,a... y){while(*p!=',')cout<<*p++;cout<<'='<<x<<',';_(p+1,y...);}
#else
#define dbg(...) 0
#endif

const int N = 1e5 + 10;
int n, q, id = 1, cnt = 0;
int head[N], to[2 * N], nx[2 * N], fa[N], dep[N], dfn[N], son[N], tp[N], sz[N], mk[N], a[N];

void ad(int x, int y) {
    to[id] = y;
    nx[id] = head[x];
    head[x] = id++;
}

void dfs1(int cur, int f) {
    dep[cur] = dep[f] + 1;
    fa[cur] = f;
    sz[cur] = 1;
    for (int i = head[cur]; i > 0; i = nx[i]) {
        int u = to[i];
        if (u == f) {
            continue;
        }
        dfs1(u, cur);
        if (sz[u] > sz[son[cur]]) {
            son[cur] = u;
        }
        sz[cur] += sz[u];
    }
}

void dfs2(int cur, int f) {
    cnt++;
    dfn[cur] = cnt;
    tp[cur] = f;
    if (son[cur] == 0) return; 
    dfs2(son[cur], f);
    for (int i = head[cur]; i > 0; i = nx[i]) {
        int u = to[i];
        if (u == fa[cur] || u == son[cur]) {
            continue;
        }
        dfs2(u, u);
    }
}

int tree[4 * N];
void up(int p) {
    tree[p] = max(tree[p << 1], tree[p << 1 | 1]);
}

void build(int p, int l, int r, vector<int>& b) {
    if (l == r) {
        tree[p] = b[l];
        return;
    }
    int mid = l + r >> 1;
    build(p << 1, l, mid, b);
    build(p << 1 | 1, mid + 1, r, b);
    up(p);
}

void update(int loc, int v, int p, int l, int r) {
    if (l == r) {
        tree[p] += v;
        return;
    }
    int mid = l + r >> 1;
    if (loc <= mid) {
        update(loc,v,p<<1,l,mid);
    } else {
        update(loc,v,p<<1|1,mid+1,r);
    }
    up(p);
}

void update(int loc, int v) {
    update(loc, v, 1, 1, n);
}

int query(int ql, int qr, int p, int l, int r) {
    if (l > qr || r < ql) return 0;
    if (l >= ql && r <= qr) {
        return tree[p];
    }
    int mid = l + r >> 1;
    return max(query(ql, qr, p << 1, l, mid), query(ql, qr, p << 1 | 1, mid + 1, r));
}

int query(int ql, int qr) {
    return query(ql, qr, 1, 1, n);
}

int mxqr(int x, int y) {
    int res = 0;
    while (tp[x] != tp[y]) {
        if (dep[tp[x]] < dep[tp[y]]) {
            swap(x, y);
        }
        res = max(res, query(dfn[tp[x]],dfn[x]));
        res = max(res,a[tp[x]]+ mk[fa[tp[x]]]);
        x = fa[tp[x]];
    }
    if (dep[x] > dep[y]) {
        swap(x,y);
    }
    res = max(res, query(dfn[x],dfn[y]));
    if (x == tp[x]) res = max(res,a[x] + mk[fa[x]]);
    return res;
}


void solve() {
    cin >> n >> q;
    id = 1, cnt = 0;
    vector<int> b(n+1);
    for (int i = 0; i <= n; i++) {
        mk[i] = 0;
        head[i] = son[i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        ad(u,v);
        ad(v,u);
    }
    dfs1(1,0);
    dfs2(1,1);
    for (int i = 1; i <= n; i++) {
        b[dfn[i]] = a[i];
    }
    build(1,1,n,b);
    int op, x, y;
    while (q--) {
        cin >> op >> x >> y;
        if (op == 1) {
            cout << mxqr(x,y) << '\n';
        } else {
            if (fa[x]) {
                update(dfn[fa[x]],y);
                a[fa[x]] += y;
            }
            if (son[x]) {
                update(dfn[son[x]],y);
                a[son[x]] += y;
            }
            mk[x] += y;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int tt = 1;
    cin >> tt;
    while (tt--) solve();
    return 0;
}