P2305 [NOI2014] 购票

传送门

思路

先不考虑距离的限制，我们有转移方程：

\[dp_i = dp_j+p_i(dis_i-dis_j)+q_i \]

其中，\(dis_i\) 表示根到 \(i\) 的距离

那么我们就有朴素的斜率优化模型：

\[\begin{aligned} dp_i-q_i-p_idis_i&=dp_j-p_idis_j\\\\ x&=p_i\\ k&=-dis_j\\ b&=dp_j \end{aligned}\]

但现在有了距离的限制，让我们感到十分棘手

于是 lby 大佬给出了一个树套树的做法 （之前说的让树套树吃灰寄了，终究是让自己成为讨厌的人）

我们先进行树链剖分，将树划分成不超过 \(log\ n\) 条链，并编号

然后建线段树，树上的每个结点代表一棵李超线段树（李超树上的结点需要动态开店）

当我们要求结点 \(u\) 的最小费用时，我们就从它所在的链往上跳，如果当前链的任意结点到 \(u\) 的距离都不超过 \(lim_u\) ，就在线段树区间 \(dfn[l]\) ~ \(dfn[r]\) 上的李超树查询最小值

注意：最后一条链虽然不能整条链满足 \(lim_u\) 的限制，但可能某一段还是可以满足的，所以需要二分出这个结点，再求一次最小值

求完最小费用后，我们就更新线段树，所有包含 \(dfn[u]\) 的线段树区间上的李超树都要进行更新（常规的树套树）

最后注意一个坑点：\(x\) 有可能为 \(0\) ，查询/修改李超树时初始区间应为 \([0,p_{max}]\)

复杂度为 \(O(nlog^3n)\)，但因为跑不满+数据太水，最慢的点也只跑了 \(460ms\)

代码

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
inline LL reads()
{
    LL sign = 1, re = 0; char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') sign = -1; c = getchar();}
    while('0' <= c && c <= '9'){re = re * 10ll + (c - '0'); c = getchar();}
    return sign * re;
}
const int N = 2e5, M = 1e6;
const LL INF = 1e18;
int n, t; LL dp[N + 5];
struct Node
{
    int fa; LL p, q, lim, dis;
}a[N + 5];
struct Rood
{
    int to, next;
}r[N + 5]; int he[N + 5];
int hs[N + 5], si[N + 5], hf[N + 5], dfn[N + 5], cnt;
void dfs(int now)
{
    si[now] = 1;
    for(int i = he[now]; i; i = r[i].next)
    {
        int to = r[i].to;
        dfs(to); si[now] += si[to];
        if(si[to] > si[hs[now]]) hs[now] = to;
    }
}
void relabel(int now)
{
    dfn[now] = ++cnt;
    if(hs[a[now].fa] == now) hf[now] = hf[a[now].fa];
    else hf[now] = now;
    if(hs[now]) relabel(hs[now]);
    for(int i = he[now]; i; i = r[i].next)
    {
        int to = r[i].to;
        if(to == hs[now]) continue;
        relabel(to);
    }
}
LL k[N + 5], b[N + 5];
namespace Seg_Tree
{
    int tr[M << 4 | 5], ls[M << 4 | 5], rs[M << 4 | 5], he[N << 2 + 5];
    int cnt;
    void update(int &now, int l, int r, int id)
    {
        if(!now)
        {
            now = ++cnt;
            tr[now] = id;
            return;
        }
        int mid = (l + r) >> 1;
        LL L1 = k[id] * l + b[id], R1 = k[id] * r + b[id];
        LL L2 = k[tr[now]] * l + b[tr[now]], R2 = k[tr[now]] * r + b[tr[now]];
        if(L1 >= L2 && R1 >= R2) return;
        if(L1 <= L2 && R1 <= R2) {tr[now] = id; return;}
        double its = 1.0 * (b[tr[now]] - b[id]) / (k[id] - k[tr[now]]);
        if(its <= mid)
            if(L1 > L2) update(ls[now], l, mid, tr[now]), tr[now] = id;
            else update(ls[now], l, mid, id);
        else
            if(R1 > R2) update(rs[now], mid + 1, r, tr[now]), tr[now] = id;
            else update(rs[now], mid + 1, r, id);
    }
    void add(int now, int l, int r, int to)
    {
        update(he[now], 0, M, to);
        if(l == r) return;
        int mid = (l + r) >> 1;
        if(to <= mid) add(now << 1, l, mid, to);
        else add((now << 1) | 1, mid + 1, r, to);
    }
    LL query(int now, int l, int r, int to)
    {
        if(!now) return INF;
        if(l == r) return k[tr[now]] * to + b[tr[now]];
        int mid = (l + r) >> 1;
        if(to <= mid) return std::min(k[tr[now]] * to + b[tr[now]], query(ls[now], l, mid, to));
        else return std::min(k[tr[now]] * to + b[tr[now]], query(rs[now], mid + 1, r, to));
    }
    LL get_ans(int now, int l, int r, int L, int R, int to)
    {
        if(L <= l && r <= R) return query(he[now], 0, M, to);
        int mid = (l + r) >> 1; LL re = INF;
        if(L <= mid) re = std::min(re, get_ans(now << 1, l, mid, L, R, to));
        if(mid < R) re = std::min(re, get_ans((now << 1) | 1, mid + 1, r, L, R, to));
        return re;
    }
}
using Seg_Tree::add; using Seg_Tree::get_ans;
inline void solve(int i)
{
    dp[i] = INF; int l, r;
    for(l = hf[a[i].fa], r = a[i].fa; r && a[i].dis - a[l].dis <= a[i].lim; r = a[l].fa, l = hf[r])
        dp[i] = std::min(dp[i], get_ans(1, 1, n, dfn[l], dfn[r], a[i].p));
    if(!r || a[i].dis - a[r].dis > a[i].lim) return;
    int L = l, R = r;
    while(L + 1 < R)
    {
        int mid = (L + R) >> 1;
        if(a[i].dis - a[mid].dis <= a[i].lim) R = mid;
        else L = mid;
    }
    dp[i] = std::min(dp[i], get_ans(1, 1, n, dfn[R], dfn[r], a[i].p));
}
void DP(int now)
{
    if(now != 1) solve(now);
    dp[now] += a[now].q + a[now].dis * a[now].p;
    k[dfn[now]] = -a[now].dis, b[dfn[now]] = dp[now]; add(1, 1, n, dfn[now]);
    for(int i = he[now]; i; i = r[i].next)
    {
        int to = r[i].to;
        DP(to);
    }
}
signed main()
{
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = reads(), t = reads();
    for(int i = 2; i <= n; i++)
    {
        int fa = reads(); LL s = reads(), p = reads(), q = reads(), lim = reads();
        a[i] = (Node){fa, p, q, lim, a[fa].dis + s};
        r[i - 1] = (Rood){i, he[fa]}; he[fa] = i - 1;
    }
    dfs(1);
    relabel(1);
    DP(1);
    for(int i = 2; i <= n; i++)
        printf("%lld\n", dp[i]);
    return 0;
}
luogu题解树链剖分树套树斜率优化

相关

LG5308 [COCI2019] Quiz（wqs二分+斜率优化DP）

斜率优化

bzoj4811 [Ynoi2017]由乃的OJ 树链剖分+贪心+二进制

斜率优化

Codeforces 856D - Masha and Cactus（树链剖分优化 dp）

算法学习笔记之斜率优化

LCA——树链剖分

[bzoj] 1597 土地购买 || 斜率优化dp

数据结构专题-专项训练：树链剖分

2568. 树链剖分

树链剖分&动态树学习笔记

BZOJ1767 [CEOI2009] Harbingers - 树上斜率优化

标签