LOJ6678 礼物题解

题意：

穷愁潦倒的小 B 正在树上漫步，突然接到了小 S 的电话，要他去点 $y$ 买一些礼物，然而他现在正处于 $x$ 点，并且他身上并没有钱。

小 L 告诉了他一个绝妙的方法。树上的每个点都有大佬的存在，其中一些大佬会购买或出售（售价与收购价相同）bsoj 权限账号。而且各点 dalao 数量不同，价格也不同，这样的交易能使他赚上一笔差价。小 S 没有告诉他礼物的价钱，他只能赚尽量多的钱。由于小 S 在小 B 的身上装了追踪器，所以他只能走 $x$ 到 $y$ 的最短路，而且时间不足，因此这样的交易只能发生一次（指买一次卖一次）。

小 B 这样的大神犇显然已经知道求解方法了，但他为了不被小 S 发现，让你来帮他解决这个问题。

输入格式：

输入第一行是一个整数 $n$ ，表示树上的点数。

接下来 $n$ 个正整数，表示每个点上权限号的价格。

接下来 $n-1$ 行，每行两个整数 $x, y$ ，表示第 $x$ 点和第 $y$ 点有一条边。

接下来一个整数 $m$ ，表示接下来有 $m$ 个询问。

接下来有 $m$ 行，每行两个整数 $x$ 和 $y$ ，表示小 $B$ 从第 $x$ 点出发要到第 $y$ 点。

输出格式：

输出包括 $m$ 行。每行对应一个询问，一个整数，表示小 B 最多能赚到多少钱。

又是经典的“分情况跳链”，即根据链的倾斜方向选择合并方式，做了不下三道题了。

考虑树剖+线段树维护区间最大值、最小值、dfn 小到 dfn 大的答案，dfn 大到 dfn 小的答案

时间复杂度 $\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)(3e5 + 15))
#define ls(at) ((at) << 1)
#define rs(at) ((at) << 1 | 1)

struct Edge { int u,v,next; } e[N * 2];
struct node { int mx,mn,res1,res2; } tr[N * 4];
int n,Q,pos=1,val[N],a[N],id[N],head[N],top[N],dep[N],fa[N],sz[N],son[N];
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; val[tim] = a[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 l, node r)
{
    node c;
    up(c.mx = l.mx, r.mx); down(c.mn = l.mn, r.mn);
    c.res1 = max({l.res1, r.res1, r.mx - l.mn});
    c.res2 = max({l.res2, r.res2, l.mx - r.mn});
    return c;
}
void push_up(int at) { tr[at] = merge(tr[ls(at)], tr[rs(at)]); }
void build(int l,int r,int at)
{
    if(l == r) { return tr[at] = {val[l], val[l], 0, 0}, void(0); }
    int mid = (l + r) >> 1; build(l,mid,ls(at)); build(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];
    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,V; U = 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]];
        }
    }
    // 观察 x,y 在同一重链时的倾斜方向，并且两者的 res1 是反向的
    if(dep[x] > dep[y]) {
        U = merge(query(id[y], id[x]), U); swap(U.res1, U.res2);
        return merge(U,V).res1;
    }else {
        V = merge(query(id[x], id[y]), V); swap(V.res1, V.res2);
        return merge(V,U).res2;
    }
    return -1;
}
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 >> a[i];
    for(int i = 1, u,v; i < n; i++) {
        cin >> u >> v; addEdge(u,v); addEdge(v,u);
    }
    cin >> Q; dfs(1,0,1); dfs(1,1); build(1,n,1);
    for(int x,y; Q--; ) {
        cin >> x >> y; cout << qRange(x,y) << '\n';
    }
    return 0;
}