树剖不多说，最大字段和我这里使用的是动态DP+半群优化思想去合并的。

唯一需要注意的是，查询路径时，一定要注意半群信息的合并顺序是正确的才行。以下给一个从 luogu 不知道哪个讨论区流传下来可以测信息合并顺序 bug 的数据。

输入

20
-4 -4 -2 -2 -3 2 2 3 7 5 -4 4 7 -4 -3 5 7 2 5 8
12 7
10 17
3 19
19 15
3 1
19 13
8 3
17 4
15 18
12 9
2 4
19 16
5 7
3 7
9 11
18 6
14 4
18 17
20 4
10
1 18 4
1 8 3
2 15 14 -2
2 13 16 4
1 16 1
2 19 13 3
2 11 13 -4
1 11 11
1 10 4
1 18 9

输出

9
3
8
0
5
0

代码

const int N = 100010;
const int INF = 1000000000;
struct info
{
    int a, b, c, d;
    info() { a = 0, b = c = d = -INF; }
    info(int x, int k) { a = k * x, b = c = d = (x >= 0) ? k * x : x; }
    info operator*(const info& o)
    {
        info ret;
        ret.a = a + o.a, ret.b = std::max(a + o.b, b);
        ret.c = std::max(c + o.a, o.c), ret.d = std::max({ c + o.b, o.d, d });
        return ret;
    }
    int max_val() const { return std::max(c, d); }
};
int a[N];
namespace seg
{
    int* rev_dfn, n;
    struct node
    {
        int lc, rc;
        bool has_tag;
        int tag_set;
        info sum, rev_sum;
    } tr[N << 1];
    int rt[N], L[N], R[N], cnt;
    void init_sz(int _n) { n = _n; }
    void pushup(int u)
    {
        tr[u].sum = tr[tr[u].lc].sum * tr[tr[u].rc].sum; // up to down
        tr[u].rev_sum = tr[tr[u].rc].rev_sum * tr[tr[u].lc].rev_sum; // down to up
    }
    void upd_set(int u, int l, int r, int val_set)
    {
        tr[u].sum = tr[u].rev_sum = info(val_set, r - l + 1);
        tr[u].tag_set = val_set, tr[u].has_tag = 1;
    }
    void pushdown(int u, int l, int r)
    {
        int m = (l + r) >> 1;
        if (tr[u].has_tag)
        {
            upd_set(tr[u].lc, l, m, tr[u].tag_set);
            upd_set(tr[u].rc, m + 1, r, tr[u].tag_set);
            tr[u].has_tag = 0;
        }
    }
    int _build(int l, int r)
    {
        int u = ++cnt;
        if (l == r)
            return tr[u].sum = tr[u].rev_sum = info(a[rev_dfn[l]], 1), u;
        int m = (l + r) >> 1;
        tr[u].lc = _build(l, m), tr[u].rc = _build(m + 1, r);
        return pushup(u), u;
    }
    void build(int i, int l, int r) { L[i] = l, R[i] = r, rt[i] = _build(L[i], R[i]); }
    void _upd(int u, int l, int r, int L, int R, int val_set)
    {
        if (l > R || r < L || l > r)
            return;
        if (l <= L && R <= r)
        {
            upd_set(u, L, R, val_set);
            return;
        }
        pushdown(u, L, R);
        int M = (L + R) >> 1;
        _upd(tr[u].lc, l, r, L, M, val_set), _upd(tr[u].rc, l, r, M + 1, R, val_set);
        pushup(u);
    }
    void upd(int i, int l, int r, int val_set) { _upd(rt[i], l, r, L[i], R[i], val_set); }
    info _query(int u, int l, int r, int L, int R, bool flag) // flag 1 : sum 0 : rev_sum
    {
        if (l > R || r < L || l > r)
            return info();
        if (l <= L && R <= r)
            return flag ? tr[u].sum : tr[u].rev_sum;
        pushdown(u, L, R);
        int M = (L + R) >> 1;
        if (flag)
            return _query(tr[u].lc, l, r, L, M, flag) * _query(tr[u].rc, l, r, M + 1, R, flag);
        else
            return _query(tr[u].rc, l, r, M + 1, R, flag) * _query(tr[u].lc, l, r, L, M, flag);
    }
    info query(int i, int l, int r, bool flag) { return _query(rt[i], l, r, L[i], R[i], flag); }
}
namespace HLD
{
    int n, rt;
    int to[N << 1], nxt[N << 1], h[N], ecnt;
    void add_edge(int u, int v) { to[++ecnt] = v, nxt[ecnt] = h[u], h[u] = ecnt; }
    void link(int u, int v) { add_edge(u, v), add_edge(v, u); }

    int f[N], sz[N], dep[N], son[N];
    int dfn[N], rev_dfn[N], top[N], bot[N], dfst;
    void dfs1(int u, int fa)
    {
        f[u] = fa, sz[u] = 1, dep[u] = dep[fa] + 1;
        for (int i = h[u]; i; i = nxt[i])
        {
            int v = to[i];
            if (v == fa)
                continue;
            dfs1(v, u), sz[u] += sz[v];
            if (sz[son[u]] < sz[v])
                son[u] = v;
        }
    }
    void dfs2(int u, int topf)
    {
        top[u] = topf, dfn[u] = ++dfst, rev_dfn[dfst] = u;
        if (son[u])
            dfs2(son[u], topf), bot[u] = bot[son[u]];
        else
            bot[u] = u;
        for (int i = h[u]; i; i = nxt[i])
        {
            int v = to[i];
            if (v == f[u] || v == son[u])
                continue;
            dfs2(v, v);
        }
    }
    void build(int _rt, int _n)
    {
        n = _n, rt = _rt;
        dfs1(rt, 0), dfs2(rt, rt), seg::rev_dfn = rev_dfn;

        for (int i = 1; i <= n; ++i)
            if (top[i] == i)
                seg::build(i, dfn[i], dfn[bot[i]]);
    }
    int lca(int u, int v)
    {
        while (top[u] ^ top[v])
        {
            if (dep[f[top[u]]] < dep[f[top[v]]])
                std::swap(u, v);
            u = f[top[u]];
        }
        if (dep[u] > dep[v])
            std::swap(u, v);
        return u;
    }
    void modify(int u, int v, int val_set)
    {
        while (top[u] ^ top[v])
        {
            if (dep[f[top[u]]] < dep[f[top[v]]])
                std::swap(u, v);
            seg::upd(top[u], dfn[top[u]], dfn[u], val_set);
            u = f[top[u]];
        }
        if (dep[u] > dep[v])
            std::swap(u, v);
        seg::upd(top[u], dfn[u], dfn[v], val_set);
    }
    info query_chain(int u, int tp, bool flag) // flag : 1 tp->u 0 u->tp
    {
        info ret = info();
        while (top[u] ^ top[tp])
        {
            if (dep[f[top[u]]] < dep[f[top[tp]]])
                std::swap(u, tp);
            ret = flag ? (seg::query(top[u], dfn[top[u]], dfn[u], flag) * ret) : (ret * seg::query(top[u], dfn[top[u]], dfn[u], flag));
            u = f[top[u]];
        }
        if (dep[u] > dep[tp])
            std::swap(u, tp);
        ret = flag ? (seg::query(top[u], dfn[u] + flag, dfn[tp], flag) * ret) : (ret * seg::query(top[u], dfn[u] + flag, dfn[tp], flag));
        return ret;
    }
    info query_route(int u, int v)
    {
        int l = lca(u, v);
        return query_chain(u, l, 0) * query_chain(v, l, 1);
    }
}
int main()
{
    int n = rd();
    for (int i = 1; i <= n; ++i)
        a[i] = rd();
    for (int i = 1; i < n; ++i)
        HLD::link(rd(), rd());
    HLD::build(1, n);
    int q = rd(), op = 0, u = 0, v = 0;
    while (q--)
    {
        op = rd(), u = rd(), v = rd();
        if (op & 1)
            wr(std::max(HLD::query_route(u, v).max_val(), 0)), putchar('\n');
        else
            HLD::modify(u, v, rd());
    }
}