SP6779 GSS7 - Can you answer these queries VII 题解

题目链接：SP6779 GSS7 - Can you answer these queries VII

题意：

给定一棵树，有 \(N~(N \le 100000)\) 个节点，每一个节点都有一个权值 \(x_i (|x_i| \le 10000)\)

你需要执行 \(Q~(Q \le 100000)\) 次操作：

1. 1 a b 查询 (a,b) 这条链上的最大子段和，可以为空（即输出 \(0\) ）
2. 2 a b c 将 (a,b) 这条链上的所有点权变为c \((|c| \le 10000)\)

输入格式：

第一行一个整数 \(N\)

接下来一行有 \(N\) 个整数表示 \(x_i\)

接下来 \(N-1\) 行，每行两个整数 \(u,v\) 表示 \(u\) 和 \(v\) 之间有一条边相连

接下来一行一个整数 \(Q\)

之后有 \(Q\) 行，每行诸如 1 a b 或者 2 a b c

输出格式：

对于每一个询问，输出答案。

首先套路地树剖一下，把问题转到区间上。

最大子段和在前几道题都快写烂了，不过带区间推平操作的怎么做呢？

其实也很简单，区间推平以后，区间的几乎所有信息都是重复的了，没了。

对于维护前后缀信息的线段树，树剖调重链的时候要分别处理，这个也是写烂了。

不过这个题其实不是真正的最大子段和，因为它可以一个数都不选！！答案为 \(0\) ！！

时间复杂度 \(\mathcal{O}(n \log^2 n)\)

代码：（树剖真的无聊）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))
#define ls(at) ((at) << 1)
#define rs(at) ((at) << 1 | 1)

struct Edge { int u,v,next; } e[N * 2];
struct node { int sum, lmx, rmx, res, tag=INF; } tr[N * 4];
int n,Q,pos=1,head[N],a[N],val[N],dep[N],id[N],sz[N],fa[N],son[N],top[N];
void addEdge(int u,int v) { e[++pos] = {u,v,head[u]}; head[u] = pos; }
void push_up(int at)
{
    node &l = tr[ls(at)], &r = tr[rs(at)], &x = tr[at];
    x.sum = l.sum + r.sum; up(x.lmx = l.lmx, l.sum + r.lmx); x.tag = INF;
    up(x.rmx = r.rmx, r.sum + l.rmx); up(x.res = l.rmx + r.lmx, max(l.res, r.res));
}
node merge(node l, node r)
{
    node x; x.sum = l.sum + r.sum; up(x.lmx = l.lmx, l.sum + r.lmx); x.tag = INF;
    up(x.rmx = r.rmx, r.sum + l.rmx); up(x.res = l.rmx + r.lmx, max(l.res, r.res)); return x;
}
void build(int l = 1,int r = n,int at = 1)
{
    if(l == r) { tr[at] = {a[l], a[l], a[l], a[l], INF}; return; }
    int mid = (l + r) >> 1; build(l,mid,ls(at)); build(mid+1,r,rs(at)); push_up(at);
}
void proc(int l,int r,int k,int at)
{
    int sum = k * (r - l + 1), mx = max(sum, 0ll);
    tr[at] = {sum, mx, mx, mx, k}; 
}
void push_down(int l,int r,int at)
{
    int k = tr[at].tag; if(k == INF) return; tr[at].tag = INF;
    int mid = (l + r) >> 1; proc(l,mid,k,ls(at)); proc(mid+1,r,k,rs(at)); 
}
void update(int nl,int nr,int k, int l = 1, int r = n, int at = 1)
{
    if(nl <= l && r <= nr)
    {
        int sum = k * (r - l + 1), mx = max(sum, 0ll);
        tr[at] = {sum, mx, mx, mx, k}; return;
    }
    push_down(l,r,at);int mid = (l + r) >> 1;
    if(nl <= mid) update(nl, nr, k, l, mid, ls(at));
    if(nr > mid) update(nl, nr, k, mid + 1, r, rs(at));
    push_up(at);
}
node query(int nl,int nr,int l = 1,int r = n,int at = 1)
{
    if(nl <= l && r <= nr) return tr[at];
    push_down(l,r,at); int mid = (l + r) >> 1;
    if(nl > mid) return query(nl, nr, mid + 1, r, rs(at));
    if(nr <= mid) return query(nl, nr, l, mid, ls(at));
    return merge(query(nl, nr, l, mid, ls(at)), query(nl, nr, mid + 1, r, rs(at)));
}
void dfs(int u,int f,int d)
{
    dep[u] = d; sz[u] = 1; fa[u] = f; int mx = -1;
    for(int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].v; if(v == f) continue;
        dfs(v,u,d+1); sz[u] += sz[v]; if(sz[v] > mx) { son[u] = v, mx = sz[v]; }
    }
}
void dfs(int u,int ftop)
{
    static int tim = 0; id[u] = ++tim; a[tim] = val[u]; top[u] = ftop;
    if(son[u]) dfs(son[u], ftop);
    for(int i = head[u],v; i; i = e[i].next) { v = e[i].v; if(v != fa[u] && v != son[u]) dfs(v,v); }
}
void upRange(int x,int y,int k)
{
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) swap(x,y);
        update(id[top[x]], id[x], k); x = fa[top[x]];
    }
    if(id[x] > id[y]) { swap(x,y); }  update(id[x], id[y], k);
}
int qRange(int x,int y)
{
    node U = {0, 0, 0, 0}, V = {0, 0, 0, 0};
    while(top[x] != top[y])
    {
        if(dep[top[x]] > dep[top[y]]) {
            U = merge(query(id[top[x]], id[x]), U); x = fa[top[x]];
        }else {
            V = merge(query(id[top[y]], id[y]), V); y = fa[top[y]];
        }
    }
    if(id[x] < id[y]) {
        V = merge(query(id[x], id[y]), V);
        swap(V.lmx, V.rmx); return merge(V,U).res;
    }else {
        U = merge(query(id[y], id[x]), U);
        swap(U.lmx, U.rmx); return merge(U,V).res;
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> val[i];
    for(int i = 1,u,v; i < n; i++) {
        cin >> u >> v; addEdge(u,v); addEdge(v,u);
    }
    dfs(1,0,1); dfs(1,1); build(); cin >> Q;
    for(int op,x,y,z; Q--; )
    {
        if(cin >> op, op == 1) {
            cin >> x >> y; cout << qRange(x,y) << '\n';
        }else {
            cin >> x >> y >> z; upRange(x,y,z);
        }
    }
    return 0;
}