题解：P11343 [KTSC 2023 R1] 出租车旅行

· · 题解

经过路径中除了终点外，其他点的 b 应该单调下降。

按照 b 从大到小 DP，可以得到 f_i = \min \limits_{j} \{f_j + a_j + b_j \times \mathrm{dis}(i,j)\}。

这个 DP 直接点分树每个点维护子树的动态开点李超树就行。由于这里加入的直线是全局加入，所以李超树是一个 \log 的，总复杂度 O(n \log n \log V)。

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

constexpr int N = 1e5 + 5, M = 1e7 + 5;

std::vector<long long> travel(std::vector<long long> A, std::vector<int> B, std::vector<int> U, std::vector<int> V, std::vector<int> W);

int n, wc, tot;
array<ll, N> a, b, ans;
array<vector<pair<int, ll>>, N> G;
array<vector<int>, N> NG;
array<array<int, 20>, N> faf;
array<int, N> dep, sz, vis, dfa;
array<ll, N> dist, f;

void dfs(int u, int fa)
{
    faf[u][0] = fa;
    dep[u] = dep[fa] + 1;
    for (auto &[j, w] : G[u])
    {
        if (j ^ fa) dist[j] = dist[u] + w, dfs(j, u);
    }
}

inline int LCA(int u, int v)
{
    if (dep[u] < dep[v]) swap(u, v);
    int k = dep[u] - dep[v], c = 0;
    while (k)
    {
        if (k & 1) u = faf[u][c];
        k >>= 1;
        c++;
    }
    if (u == v) return u;
    for (int i = 19; i >= 0; i--) if (faf[u][i] ^ faf[v][i]) u = faf[u][i], v = faf[v][i];
    return faf[u][0];
}

inline ll qdis(int u, int v){return dist[u] + dist[v] - 2ll * dist[LCA(u, v)];}

inline void dfs2(int u, int fa)
{
    sz[u] = 0;
    if (vis[u]) return;
    sz[u] = 1;
    for (auto &[j, w] : G[u])
    {
        if (j ^ fa)
        {
            dfs2(j, u);
            sz[u] += sz[j];
        }
    }
}

inline void dfs3(int u, int fa)
{
    if (vis[u]) return;
    int maxn = tot - sz[u];
    for (auto &[j, w] : G[u])
    {
        if (j == fa) continue;
        dfs3(j, u);
        maxn = max(maxn, sz[j]);
    }
    if (maxn <= (tot >> 1)) wc = u;
}

inline void dc(int u, int fav)
{
    if (vis[u]) return;
    dfs2(u, 0);
    tot = sz[u];
    dfs3(u, 0);
    u = wc;
    vis[u] = 1;
    if (~fav) NG[fav].emplace_back(u), dfa[u] = fav;
    for (auto &[j, w] : G[u]) dc(j, u);
}

class Lichao_SegmentTree
{
public:
    int idx;
    struct Node
    {
        int ls, rs;
        ll k, b; // kx + b
        Node()
        {
            ls = rs = k = 0, b = (ll)3e18;
        }
    };
    array<Node, M> tr;
    inline void crt(int u)
    {
        if (!tr[u].ls) tr[u].ls = ++idx;
        if (!tr[u].rs) tr[u].rs = ++idx;
    }
    inline ll qry(ll k, ll b, ll x)
    {
        return k * x + b;
    }
    inline void pushtag(int u, ll l, ll r, ll k, ll b)
    {
        ll mid = l + r >> 1;
        if (qry(k, b, l) <= qry(tr[u].k, tr[u].b, l) && qry(k, b, r) <= qry(tr[u].k, tr[u].b, r))
        {
            tr[u].k = k, tr[u].b = b;
            return;
        }
        else if (qry(k, b, l) >= qry(tr[u].k, tr[u].b, l) && qry(k, b, r) >= qry(tr[u].k, tr[u].b, r)) return;
        if (qry(k, b, mid) < qry(tr[u].k, tr[u].b, mid))
        {
            swap(k, tr[u].k);
            swap(b, tr[u].b);
            crt(u);
            if (qry(k, b, r) < qry(tr[u].k, tr[u].b, r)) pushtag(tr[u].rs, mid + 1, r, k, b);
            if (qry(k, b, l) < qry(tr[u].k, tr[u].b, l)) pushtag(tr[u].ls, l, mid, k, b);
        }
        else
        {
            crt(u);
            if (qry(k, b, r) < qry(tr[u].k, tr[u].b, r)) pushtag(tr[u].rs, mid + 1, r, k, b);
            if (qry(k, b, l) < qry(tr[u].k, tr[u].b, l)) pushtag(tr[u].ls, l, mid, k, b);
        }
    }
    inline void ins(int& u, ll k, ll b)
    {
        if (!u) u = ++idx;
        pushtag(u, 1ll, (ll)1e11, k, b);
    }
    inline ll query(int u, ll l, ll r, ll x)
    {
        if (!u) return (ll)3e18;
        ll res = qry(tr[u].k, tr[u].b, x);
        if (l == r) return res;
        ll mid = l + r >> 1;
        if (x <= mid) res = min(res, query(tr[u].ls, l, mid, x));
        else res = min(res, query(tr[u].rs, mid + 1, r, x));
        return res;
    }
}sgt;

array<int, N> rt, p;

inline void upd(int u, ll val)
{
    f[u] = val;
    for (int x = u; x; x = dfa[x])
    {
        sgt.ins(rt[x], b[u], f[u] + a[u] + qdis(u, x) * b[u]);
    }
}

inline ll query(int u)
{
    ll res = (ll)3e18;
    for (int x = u; x; x = dfa[x]) res = min(res, sgt.query(rt[x], 1, (ll)1e11, qdis(u, x)));
    return res;
}

std::vector<long long> travel(std::vector<long long> A, std::vector<int> B, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    n = A.size();
    for (int i = 1; i <= n; i++) a[i] = A[i - 1], b[i] = B[i - 1];
    for (int i = 0; i < n - 1; i++)
    {
        G[U[i] + 1].emplace_back(V[i] + 1, W[i]);
        G[V[i] + 1].emplace_back(U[i] + 1, W[i]);
    }
    dfs(1, 0);
    for (int j = 1; j < 20; j++) for (int i = 1; i <= n; i++) faf[i][j] = faf[faf[i][j - 1]][j - 1];
    dc(1, -1);
    for (int i = 1; i <= n; i++) p[i] = i, f[i] = (ll)3e18;
    upd(1, 0);
    sort(p.begin() + 1, p.begin() + n + 1, [&](const int& x, const int& y){return b[x] > b[y];});
    for (int i = 1; i <= n; i++)
    {
        int j = p[i];
        if (j != 1) upd(j, query(j));
    }
    vector<ll> ret;
    for (int i = 2; i <= n; i++)
    {
        ans[i] = min(f[i], query(i));
        ret.emplace_back(ans[i]);
    }
    return ret;
}