P3976 旅游

有方向的路径最大差与树链拼接

问题

P3976 [TJOI2015] 旅游
一棵树上的每座城市有当前宝石价格。每次从 $a$ 沿唯一简单路径走到 $b$，只能先买入一次再在之后经过的城市卖出，要求输出不亏损时的最大利润；完成询问后，路径上所有城市的价格同时增加 $v$。

数据规模：$1\le n,q\le5\times10^4$，初始价格不超过 $100$，任意时刻价格不超过 $10^9$。

区间摘要除了最大值与最小值，还要保存正向最大收益 lmx 和反向最大收益 rmx。合并左右区间时，正向收益可能来自左段、右段，或在左段最低价买入后到右段最高价卖出；反向收益则对称处理。

合并方向不能丢失。线段树区间天然按 DFS 序从左到右返回，但树链剖分中某一段可能沿着 DFS 序反向经过，此时要交换 lmx 与 rmx；多段路径也必须按真实的 $a\to b$ 顺序拼接，不能把它当成普通交换律信息。

路径整体加同一个值不会改变任意两点的价格差，因此 Lazy 只需同步增加摘要的最大值、最小值和加法标记，两个收益量保持不变。每次询问与修改均为 $O(\log^2 n)$。

实现与复盘

最初的 Info 已经接近正确，但叶子把最大利润初始化成价格，Lazy 又把累加写成覆盖，还保留了无关的取模。更核心的问题是直接复用普通 path 会在跳链时任意交换端点，只能保证覆盖集合正确，不能保证 $a\to b$ 的顺序；因此修改仍可复用无方向模板，查询必须单独维护两侧信息的拼接方向。

merge 与 push_up 看起来相似，是因为它们确实使用同一个信息合并律。最后把区间摘要独立成 Info，让 push_up 调用 merge，既避免维护两份公式，也不会把节点边界和 Lazy 状态混入纯摘要。

▶

AC 代码

#define ls ( u << 1 )
#define rs ( u << 1 | 1 )

struct SegTree {
/* ================================================== */
struct Info {
    ll mx, mn;
    ll lmx, rmx;
};

struct Node {
    int l, r;
    ll tag;
    Info info;
} tr[maxn << 2];

Info merge( const Info &a, const Info &b ) {
    Info res;
    res.mx = max( a.mx, b.mx );
    res.mn = min( a.mn, b.mn );
    res.lmx = max({ a.lmx, b.lmx, b.mx - a.mn });
    res.rmx = max({ a.rmx, b.rmx, a.mx - b.mn });
    return res;
}

Info rev( Info x ) {
    swap( x.lmx, x.rmx );
    return x;
}

void push_up( int u ) {
    tr[u].info = merge( tr[ls].info, tr[rs].info );
}

void apply( int u, ll val ) {
    tr[u].info.mx += val;
    tr[u].info.mn += val;
    tr[u].tag += val;
}

void push_down( int u ) {
    if( !tr[u].tag ) return ;
    apply( ls, tr[u].tag );
    apply( rs, tr[u].tag );
    tr[u].tag = 0;
}

void build( int u, int l, int r, ll val[] ) {
    tr[u] = { l, r, 0 };
    if( l == r ) {
        tr[u].info = { val[l], val[l], 0, 0 };
        return ;
    }
    int mid = ( l + r ) >> 1;
    build( ls, l, mid, val );
    build( rs, mid + 1, r, val );
    push_up( u );
}

void upd( int u, int l, int r, ll val ) {
    if( l <= tr[u].l && tr[u].r <= r ) {
        apply( u, val );
        return ;
    }
    push_down( u );
    int mid = ( tr[u].l + tr[u].r ) >> 1;
    if( l <= mid ) upd( ls, l, r, val );
    if( mid < r ) upd( rs, l, r, val );
    push_up( u );
}

Info ask( int u, int l, int r ) {
    if( l <= tr[u].l && tr[u].r <= r ) return tr[u].info;
    push_down( u );
    int mid = ( tr[u].l + tr[u].r ) >> 1;
    if( r <= mid ) return ask( ls, l, r );
    if( mid < l ) return ask( rs, l, r );
    return merge( ask( ls, l, r ), ask( rs, l, r ) );
}
/* ================================================== */
} seg;

#undef ls
#undef rs

vector<int> adj[maxn];

int fa[maxn], dep[maxn], siz[maxn], son[maxn];
int top[maxn], dfn[maxn], rnk[maxn], tim;

void dfs1( int u, int p ) {
    fa[u] = p;
    dep[u] = ( p == -1 ? 0 : dep[p] + 1 );
    siz[u] = 1, son[u] = -1;
    for( int v : adj[u] ) {
        if( v == p ) continue;
        dfs1( v, u );
        siz[u] += siz[v];
        if( son[u] == -1 || siz[v] > siz[son[u]] ) {
            son[u] = v;
        }
    }
}

void dfs2( int u, int t ) {
    top[u] = t, dfn[u] = ++ tim, rnk[tim] = u;
    if( son[u] != -1 ) dfs2( son[u], t );
    for( int v : adj[u] ) {
        if( v == fa[u] || v == son[u] ) continue;
        dfs2( v, v );
    }
}

// 将 u-v 路径拆成若干 DFS 序区间 [l, r]。
// F 表示一个可调用对象类型，例如 lambda。
template<class F>
void path( int u, int v, F work ) {
    while( top[u] != top[v] ) {
        if( dep[top[u]] < dep[top[v]] ) swap( u, v );
        work( dfn[top[u]], dfn[u] );
        u = fa[top[u]];
    }
    if( dep[u] > dep[v] ) swap( u, v );
    work( dfn[u], dfn[v] );
}

ll val[maxn], seq[maxn];

// 路径加
void upd_path( int u, int v, ll x ) {
    path( u, v, [&]( int l, int r ) {
        seg.upd( 1, l, r, x );
    });
}

SegTree::Info ask_path( int u, int v ) {
    if( top[u] == top[v] ) {
        if( dep[u] <= dep[v] ) {
            return seg.ask( 1, dfn[u], dfn[v] );
        } else {
            return seg.rev( seg.ask( 1, dfn[v], dfn[u] ) );
        }
    }
    if( dep[top[u]] > dep[top[v]] ) {
        auto cur = seg.rev( seg.ask( 1, dfn[top[u]], dfn[u] ) );
        return seg.merge( cur, ask_path( fa[top[u]], v ) );
    } else {
        auto cur = seg.ask( 1, dfn[top[v]], dfn[v] );
        return seg.merge( ask_path( u, fa[top[v]] ), cur );
    }
}

ll a[maxn];

void solve( ) {
    int n = read( );
    for( int i = 1; i <= n; ++ i ) a[i] = read( );

    for( int i = 1; i < n; ++ i ) {
        int u = read( ), v = read( );
        adj[u].push_back( v );
        adj[v].push_back( u );
    }

    tim = 0;
    dfs1( 1, -1 );
    dfs2( 1, 1 );

    for( int u = 1; u <= n; ++ u ) {
        seq[dfn[u]] = a[u];
    }

    seg.build( 1, 1, n, seq );

    int m = read( );
    for( int i = 1; i <= m; ++ i ) {
        int a = read( ), b = read( );
        ll v = read( );
        cout << ask_path( a, b ).lmx << '\n';
        upd_path( a, b, v );
    }
}