树剖+线段树 WA on #11 求助

#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>

#define INF 0x3f3f3f3f

#define lson 2*x
#define rson 2*x+1

using namespace std;

int n, m;
int a[100010];

struct Range
{
    int mxl, mxr;
    int mx, val;

    Range()
    {
        mxl = mxr = mx = val = 0;
    }
};

Range merge(Range x, Range y)
{
    Range ret;

    ret.mxl = max(x.mxl, x.val + y.mxl);
    ret.mxr = max(y.mxr, y.val + x.mxr);
    ret.val = x.val + y.val;
    ret.mx = max(max(x.mx, y.mx), x.mxr + y.mxl);

    return ret;
}

Range rev(Range x)
{
    Range ret;
    
    ret.mx = x.mx;
    ret.mxl = x.mxr;
    ret.mxr = x.mxl;
    ret.val = x.val;

    return ret;
}

class SegTree
{
    private:
        struct Node
        {
            int l, r;
            int lazy = INF;
            Range x;
        }p[400010];

        void setRange(int x, int k)
        {
            p[x].x.val = k * (p[x].r-p[x].l+1);
            if(k >= 0)
                p[x].x.mx = p[x].x.mxl = p[x].x.mxr = k * (p[x].r-p[x].l+1);
            else
                p[x].x.mx = p[x].x.mxl = p[x].x.mxr = 0;
        }
    
    public:
        void buildtree(int x, int l, int r)
        {
            p[x].l = l;
            p[x].r = r;
            p[x].lazy = INF;

            if(l == r)
            {
                setRange(x, a[l]);
                return;
            }

            int mid = (l+r)/2;
            buildtree(lson, l, mid);
            buildtree(rson, mid+1, r);

            p[x].x = merge(p[lson].x, p[rson].x);
        }

        void pushdown(int x)
        {
            if(p[x].lazy == INF)
                return;
            if(p[x].l == p[x].r)
            {
                p[x].lazy = INF;
                return;
            }

            setRange(lson, p[x].lazy);
            setRange(rson, p[x].lazy);

            p[lson].lazy = p[rson].lazy = p[x].lazy;
            p[x].lazy = INF;
        }

        void modify(int x, int l, int r, int k)
        {
            pushdown(x);

            if(l <= p[x].l && p[x].r <= r)
            {
                setRange(x, k);
                p[x].lazy = k;

                return;
            }

            if(l <= p[lson].r) modify(lson, l, r, k);
            if(p[rson].l <= r) modify(rson, l, r, k);

            p[x].x = merge(p[lson].x, p[rson].x);
        }

        Range query(int x, int l, int r)
        {
            pushdown(x);

            if(l <= p[x].l && p[x].r <= r)
                return p[x].x;
            
            if(r <= p[lson].r) return query(lson, l, r);
            if(p[rson].l <= l) return query(rson, l, r);
            return merge(query(lson, l, r), query(rson, l, r));
        }
}tree;

class TreeChain
{
    private:
        int cnt, head[100010];
        struct Edge
        {
            int to, nxt;
        }p[200010];
    
    public:
        int siz[100010], mxson[100010], dep[100010], val[100010];
        int dfn[100010], fa[100010], tp[100010];
        int cnt2 = 0;

        void AddEdge(int x, int y)
        {
            cnt++;
            p[cnt].to = y;

            p[cnt].nxt = head[x];
            head[x] = cnt;
        }

        void dfs1(int x)
        {
            int val = 0;
            siz[x] = 1;
            for(int i=head[x]; i!=0; i=p[i].nxt)
                if(dep[p[i].to] == 0)
                {
                    dep[p[i].to] = dep[x] + 1;
                    fa[p[i].to] = x;
                    
                    dfs1(p[i].to);
                    if(siz[p[i].to] > val)
                    {
                        val = siz[p[i].to];
                        mxson[x] = p[i].to;
                    }
                    siz[x] += siz[p[i].to];
                }
        }

        void dfs2(int x, int cur)
        {
            dfn[x] = ++cnt2;
            tp[x] = cur;

            if(mxson[x] != 0)
                dfs2(mxson[x], cur);

            for(int i=head[x]; i!=0; i=p[i].nxt)
                if(dfn[p[i].to] == 0)
                    dfs2(p[i].to, p[i].to);
        }

        void reassign()
        {
            for(int i=1; i<=n; i++)
                a[dfn[i]] = val[i];
        }

        void modify(int x, int y, int c)
        {
            while(tp[x] != tp[y])
            {
                if(dep[tp[x]] < dep[tp[y]])
                    swap(x, y);

                tree.modify(1, dfn[tp[x]], dfn[x], c);
                x = fa[tp[x]];
            }

            if(dep[x] > dep[y])
                swap(x, y);
            tree.modify(1, dfn[x], dfn[y], c);
        }

        Range query(int x, int y)
        {
            Range xRange;
            Range yRange;

            while(tp[x] != tp[y])
            {
                if(dep[tp[x]] < dep[tp[y]])
                {
                    swap(x, y);
                    swap(xRange, yRange);
                }

                xRange = merge(tree.query(1, dfn[tp[x]], dfn[x]), xRange);
                x = fa[tp[x]];
            }

            if(dep[x] > dep[y])
            {
                swap(x, y);
                swap(xRange, yRange);
            }

            yRange = merge(tree.query(1, dfn[x], dfn[y]), yRange);
            
            swap(yRange.mxl, yRange.mxr);
            
            return merge(xRange, yRange);
        }
}graph;

int main()
{
    // memset(graph.mxson, 0, sizeof(graph.mxson));

    scanf("%d", &n);
    for(int i=1; i<=n; i++)
        scanf("%d", &graph.val[i]);
    for(int i=1; i<=n-1; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        graph.AddEdge(x, y);
        graph.AddEdge(y, x);
    }

    graph.dep[1] = 1;
    graph.dfs1(1);
    graph.dfs2(1, 1);
    graph.reassign();
    tree.buildtree(1, 1, n);

    scanf("%d", &m);
    for(int i=1; i<=m; i++)
    {
        int opt, x, y, c;
        scanf("%d", &opt);
        if(opt == 1)
        {
            scanf("%d%d", &x, &y);
            printf("%d\n", graph.query(x, y).mx);
        }
        else
        {
            scanf("%d%d%d", &x, &y, &c);
            graph.modify(x, y, c);
        }
    }

    return 0;
}