（只支持微信付款）

大概就是区间最大子段和加上树剖，但是我太弱了根本调不出来。

就是这道题

（不要问我为什么没有提交记录，这只是某人的小号）

#include<iostream>
using namespace std;
const int INF = 2147483647;
int n, m, cnt, point[1000005], a[1000005], id[1000005], fa[1000005], top[1000005], siz[1000005], deep[1000005], son[1000005], head[1000005], tot;
struct road
{
    int y, nex;
}s[1000005];
void add(int i, int j)
{
    s[++tot].y = j, s[tot].nex = head[i];
    head[i] = tot;
}
struct node
{
    int sum, l, r, m, tag;
}tree[1000005];
void modify(int now, int l, int r, int w)
{
    tree[now].sum = w * (r - l + 1);
    tree[now].l = tree[now].r = tree[now].m = max(0, tree[now].sum);
    tree[now].tag = w;
}
void push_up(int now)
{
    tree[now].l = max(tree[now * 2].l, tree[now * 2].sum + tree[now * 2 + 1].l);
    tree[now].r = max(tree[now * 2 + 1].r, tree[now * 2 + 1].sum + tree[now * 2].r);
    tree[now].m = max(tree[now * 2].r + tree[now * 2 + 1].l, max(tree[now * 2].m, tree[now * 2 + 1].m));
    tree[now].sum = tree[now * 2].sum + tree[now * 2 + 1].sum;
}
void push_down(int now, int l, int r)
{
    if (tree[now].tag == INF)
        return;
    int mid = (l + r) / 2;
    modify(now * 2, l, mid, tree[now].tag);
    modify(now * 2 + 1, mid + 1, r, tree[now].tag);
    tree[now].tag = INF;
}
void build(int now, int l, int r)
{
    if (l == r)
    {
        tree[now].sum = tree[now].l = tree[now].r = tree[now].m = max(a[l], 0);
        tree[now].tag = INF;
        return;
    }
    int mid = (l + r) / 2;
    build(now * 2, l, mid);
    build(now * 2 + 1, mid + 1, r);
    push_up(now);
    tree[now].tag = INF;
}
void update(int now, int l, int r, int x, int y, int w)
{
    if (l > y || r < x)
        return;
    if (x <= l && r <= y)
    {
        modify(now, l, r, w);
        return;
    }
    push_down(now, l, r);
    int mid = (l + r) / 2;
    update(now * 2, l, mid, x, y, w);
    update(now * 2 + 1, mid + 1, r, x, y, w);
    push_up(now);
}
node query(int now, int l, int r, int x, int y)
{
    if (x <= l && r <= y)
        return tree[now];
    int mid = (l + r) / 2;
    push_down(now, l, r);
    if (x > mid)
        return query(now * 2 + 1, mid + 1, r, x, y);
    else if (y <= mid)
        return query(now * 2, l, mid, x, y);
    else
    {
        node tmpa = query(now * 2, l, mid, x, y), tmpb = query(now * 2 + 1, mid + 1, r, x, y);
        node ans = { tmpa.sum + tmpb.sum,max(tmpa.l,tmpa.sum + tmpb.l),max(tmpb.r,tmpb.sum + tmpa.r),max(max(tmpa.m,tmpb.m),tmpa.r + tmpb.l),0 };
        return ans;
    }
}
void dfs1(int now, int father)
{
    int nowson = -1;
    deep[now] = deep[father] + 1;
    fa[now] = father;
    siz[now] = 1;
    for (int i = head[now]; i; i = s[i].nex)
    {
        int y = s[i].y;
        if (y == father)
            continue;
        dfs1(y, now);
        siz[now] += siz[y];
        if (siz[y] > nowson)
            nowson = siz[y], son[now] = y;
    }
}
void dfs2(int now, int topf)
{
    id[now] = ++cnt;
    a[cnt] = point[now];
    top[now] = topf;
    if (!son[now])
        return;
    dfs2(son[now], topf);
    for (int i = head[now]; i; i = s[i].nex)
    {
        int y = s[i].y;
        if (y == fa[now] || y == son[now])
            continue;
        dfs2(y, y);
    }
}
void res1(int x, int y, int w)
{
    while (top[x] != top[y])
    {
        if (deep[top[x]] < deep[top[y]])
            swap(x, y);
        update(1, 1, n, id[top[x]], id[x], w);
        x = fa[top[x]];
    }
    if (deep[x] > deep[y])
        swap(x, y);
    update(1, 1, n, id[x], id[y], w);
}
node res2(int x, int y)
{
    node l = { 0,-INF,-INF,-INF,0 }, r = { 0,-INF,-INF,-INF,0 };
    while (top[x] != top[y])
    {
        if (deep[top[x]] > deep[top[y]])
        {
            node ano = query(1, 1, n, id[top[x]], id[x]);
            x = fa[top[x]];
            l = { l.sum + ano.sum,max(l.l,l.sum + ano.l),max(ano.r,ano.sum + l.r),max(max(l.m,ano.m),l.r + ano.l),0 };
        }
        else
        {
            node ano = query(1, 1, n, id[top[y]], id[y]);
            y = fa[top[y]];
            r = { r.sum + ano.sum,max(r.l,r.sum + ano.l),max(ano.r,ano.sum + r.r),max(max(r.m,ano.m),r.r + ano.l),0 };
        }
    }
    if (deep[x] > deep[y])
    {
        node ano = query(1, 1, n, id[y], id[x]);
        l = { l.sum + ano.sum,max(l.l,l.sum + ano.l),max(ano.r,ano.sum + l.r),max(max(l.m,ano.m),l.r + ano.l),0 };
    }
    else
    {
        node ano = query(1, 1, n, id[x], id[y]);
        r = { r.sum + ano.sum,max(r.l,r.sum + ano.l),max(ano.r,ano.sum + r.r),max(max(r.m,ano.m),r.r + ano.l),0 };
    }
    swap(l.l, l.r);
    return { l.sum + r.sum,max(l.l,l.sum + r.l),max(r.r,r.sum + l.r),max(max(l.m,r.m),l.r + r.l),0 };
}
signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> point[i];
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    build(1, 1, n);
    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        int op, u, v, w;
        cin >> op;
        if (op == 1)
        {
            cin >> u >> v;
            cout << max(res2(u, v).m, 0) << endl;
        }
        else
            cin >> u >> v >> w, res1(u, v, w);
    }
    return 0;
}