P3976 旅游 LCT

Genius_Z · 2019-04-19 15:44:25 · 题解

题意：给出一棵树，询问一条链(a,b)上满足dis(a,c)<dis(a,d)的(c,d)中最大的val(d)-val(c)

因为是求链上的信息所以容易想到LCT

我们考虑维护最大值（记为maxn），最小值（记为minn），从左到右的最大利润（记为lmax），从右到左的最大利润（记为rmax）。

维护（应该比较好理解）：

inl void maintain(int x) {
    t[x].maxn = max(max(t[ls(x)].maxn, t[rs(x)].maxn), t[x].w);
    t[x].minn = min(min(t[ls(x)].minn, t[rs(x)].minn), t[x].w);
    t[x].lmax = max(max(t[ls(x)].lmax, t[rs(x)].lmax), max(t[ls(x)].maxn, t[x].w) - min(t[rs(x)].minn, t[x].w));
    t[x].rmax = max(max(t[ls(x)].rmax, t[rs(x)].rmax), max(t[rs(x)].maxn, t[x].w) - min(t[ls(x)].minn, t[x].w));
}

维护从右到左的最大利润的原因就是交换左右儿子时左右要翻转

inl void reverse(int x) {
    swap(t[x].lmax, t[x].rmax);
    swap(ls(x), rs(x));
    t[x].filp ^= 1;
}

边界条件：

t[0].minn = inf, t[0].maxn = -inf;

Code：

#include <algorithm>
#include <tuple>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#define inl inline
#define re register int
#define fa(x) t[x].fa
#define ls(x) t[x].child[0]
#define rs(x) t[x].child[1]
#define ll long long
const int inf = 0x3f3f3f3f;
#define lowbit(x) ((x) & (-x))
using namespace std;
template <class Read>
inl Read read() {
    Read x = 0;
    register bool w = 0;
    register char c = getchar();
    while (c > '9' || c < '0') {
        if (c == '-') w = 1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return w ? -x : x;
}
struct node {
    int fa, child[2], w, maxn, minn, add, lmax, rmax;
    bool filp;
} t[1000001];
struct edge {
    int next, to;
} e[200001];
int head[100001], tot;
inl void adde(int x, int y) {
    e[++tot] = edge{ head[x], y }, head[x] = tot;
}
inl void maintain(int x) {
    t[x].maxn = max(max(t[ls(x)].maxn, t[rs(x)].maxn), t[x].w);
    t[x].minn = min(min(t[ls(x)].minn, t[rs(x)].minn), t[x].w);
    t[x].lmax = max(max(t[ls(x)].lmax, t[rs(x)].lmax), max(t[ls(x)].maxn, t[x].w) - min(t[rs(x)].minn, t[x].w));
    t[x].rmax = max(max(t[ls(x)].rmax, t[rs(x)].rmax), max(t[rs(x)].maxn, t[x].w) - min(t[ls(x)].minn, t[x].w));
}
inl void sum(int x, int w) {
    t[x].w += w, t[x].add += w, t[x].maxn += w, t[x].minn += w;
}
inl void reverse(int x) {
    swap(t[x].lmax, t[x].rmax);
    swap(ls(x), rs(x));
    t[x].filp ^= 1;
}
inl void pushdown(int x) {
    if (t[x].add) {
        if (ls(x))sum(ls(x), t[x].add);
        if (rs(x))sum(rs(x), t[x].add);
        t[x].add = 0;
    }
    if (t[x].filp) {
        if (ls(x))reverse(ls(x));
        if (rs(x))reverse(rs(x));
        t[x].filp = 0;
    }
}
inl bool nroot(int x) { return ls(fa(x)) == x || rs(fa(x)) == x; }
inl bool poi(int x) { return rs(fa(x)) == x; }
inl void push(int x) {
    if (nroot(x))push(fa(x));
    pushdown(x);
}
inl void rotate(int x) {
    re f = fa(x), gf = fa(f), fs = poi(x), gfs = poi(f), s = t[x].child[fs ^ 1];
    if (nroot(f))t[gf].child[gfs] = x;
    t[x].child[fs ^ 1] = f, t[f].child[fs] = s;
    if (s)fa(s) = f;
    fa(f) = x, fa(x) = gf;
    maintain(f);
}
inl void splay(int x) {
    push(x);
    while (nroot(x)) {
        if (nroot(fa(x)))poi(x) == poi(fa(x)) ? rotate(fa(x)) : rotate(x);
        rotate(x);
    }
    maintain(x);
}
inl void access(int x) {
    for (re i = 0; x; x = fa(i = x))splay(x), rs(x) = i, maintain(x);
}
inl void makeroot(int x) {
    access(x), splay(x), reverse(x);
}
inl void split(int x, int y) {
    makeroot(y), access(x), splay(x);
}
inl void link(int x, int y) {
    split(x, y), fa(y) = x;
}
signed main() {
    t[0].minn = inf, t[0].maxn = -inf;
    re n = read<int>();
    for (re i = 1; i <= n; i++)t[i].maxn = t[i].minn = t[i].w = read<int>();
    for (re i = 1; i < n; i++) {
        re x = read<int>(), y = read<int>();
        link(x, y);
    }
    re m = read<int>();
    while (m--) {
        re x = read<int>(), y = read<int>(), w = read<int>();
        split(x, y), printf("%d\n", t[x].lmax), sum(x, w);
    }
}