洛谷P3976 [TJOI2015]旅游 题解

题目链接：P3976 [TJOI2015]旅游

题意：

为了提高智商， cxy 准备去往一个新世界去旅游。这个世界的城市布局像一棵树，每两座城市之间只有一条路径可以互达。

每座城市都有一种宝石,有一定的价格。 cxy 为了赚取最高利益,她会选择从 A 城市买入再转手卖到 B 城市。

由于 cxy 买宝石时经常卖萌，因而凡是 cxy 路过的城市，这座城市的宝石价格会上涨。让我们来算算 cxy 旅游完之后能够赚取的最大利润。(如 A 城市宝石价格为 \(v\)，则 cxy 出售价格也为 \(v\))

输入格式：

第一行输入一个正整数 \(n\) 表示城市个数

接下来一行输入 \(n\) 个正整数表示每座城市宝石的最初价格 \(p\),每个宝石的初始价格不超过 \(100\)。

第三行开始连续输入 \(n-1\) 行,每行有两个数字 \(x\) 和 \(y\)。表示 \(x\) 城市和 \(y\) 城市有一条路径。城市编号从\(1\)开始。

下一行输入一个正整数 \(q\) 表示询问次数。

接下来 \(q\) 行每行输入三个正整数 \(a,b,v\)，表示 cxy 从 \(a\) 旅游到 \(b\)，城市宝石上涨 \(v\)。

输出格式：

对于每次询问，输出 cxy 可能获得的最大利润，如果亏本了则输出 \(0\)。

数据范围：

保证 \(1\le n,q \le 5\times 10^4\)，在任何时刻任何城市的宝石价格都不超过 \(10^9\)。

又是个题意不清的题。大概就是每次给出一条链，要你从一端走到另一端然后赚最大的差价

等你跑完这一趟以后，这个链上的每个点都加上同一个值。链加？考虑树剖。

考虑如何维护这个最大差价。直接维护最大值和最小值会导致他们的位置关系不确定

因此我们再维护个 lmx 和 rmx ，表示左边走到右边&右边走到左边的最大差价。

合并方式见代码，不过写过线段树维护最大子段和的应该都很熟悉吧（（

然后这题就没了，难度全在代码上，要注意跳 top 的时候怎么合并以及查询的时候要合并啥的。

时间复杂度 \(\mathcal{O}(n \log 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)(5e4 + 15))
#define ls(at) ((at) << 1)
#define rs(at) ((at) << 1 | 1)

struct node { int mx,mn,lmx,rmx,tag; } tr[N * 4], tmp;
int n,m,pos=1,head[N],arr[N],t[N];
int dep[N],son[N],id[N],top[N],fa[N],sz[N];
struct Edge { int u,v,next; } e[N * 2];
void addEdge(int u,int v) { e[++pos] = {u,v,head[u]}; head[u] = pos; }
void dfs(int u,int f,int d)
{
    dep[u] = d; fa[u] = f; sz[u] = 1; 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) { mx = sz[v]; son[u] = v; }
    }
}
void dfs(int u,int ftop)
{
    static int tim = 0; top[u] = ftop; id[u] = ++tim; arr[id[u]] = t[u];
    if(son[u]) dfs(son[u], ftop);
    for(int i = head[u]; i; i = e[i].next)
    { int v = e[i].v; if(v != fa[u] && v != son[u]) dfs(v,v); }
}
node merge(node a, node b)
{
    tmp.mx = max(a.mx, b.mx);
    tmp.mn = min(a.mn, b.mn);
    tmp.lmx = max({a.lmx, b.lmx, b.mx - a.mn});
    tmp.rmx = max({a.rmx, b.rmx, a.mx - b.mn});
    return tmp;
}
void push_up(int at) { tr[at] = merge(tr[ls(at)], tr[rs(at)]); tr[at].tag = 0; }
void push_down(int at)
{
    if(!tr[at].tag) return;
    tr[ls(at)].mx += tr[at].tag; tr[rs(at)].mx += tr[at].tag;
    tr[ls(at)].mn += tr[at].tag; tr[rs(at)].mn += tr[at].tag;
    tr[ls(at)].tag += tr[at].tag; tr[rs(at)].tag += tr[at].tag;
    tr[at].tag = 0;
}
void build(int at, int l, int r)
{
    if(l == r) { return tr[at] = {arr[l], arr[l], 0, 0, 0}, void(0); }
    int mid = (l + r) >> 1; build(ls(at), l, mid); build(rs(at), mid + 1, r); push_up(at);
}
void update(int nl, int nr, int k, int l = 1, int r = n, int at = 1)
{
    if(nl <= l && r <= nr)
    { return tr[at].mx += k, tr[at].mn += k, tr[at].tag += k, void(0); }
    push_down(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);
}
void upRange(int x,int y,int v)
{
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        update(id[top[x]], id[x], v); x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    update(id[x], id[y], v);
}
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(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)));
}
int qRange(int x,int y)
{
    node U = {-INF,INF,0,0}, V = {-INF,INF,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]];
        }
    }
    (dep[x] < dep[y]) ? (V = merge(query(id[x], id[y]), V)) : (U = merge(query(id[y], id[x]), U));
    return max({U.rmx, V.lmx, V.mx - U.mn});
}
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 >> t[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(1, 1, n);
    int Q; cin >> Q; for(int x,y,z; Q--;)
    {
        cin >> x >> y >> z;
        cout << qRange(x,y) << '\n'; upRange(x,y,z);
    } 
    return 0;
}