首页 > 其他分享 >【题解】P2305 [NOI2014] 购票

【题解】P2305 [NOI2014] 购票

时间:2023-01-06 13:22:05浏览次数:48  
标签:Point int 题解 ll operatorname NOI2014 depth maxn P2305

题意

给定一棵边带权且以 \(1\) 为根的树,从后代结点 \(u\) 跳到祖先结点 \(v\) 的代价为 \(dp_u + q_u\),其中 \(p_u, q_u\) 是给定的常数,\(d\) 是 \(u, v\) 的树上距离。要求只有 \(d \leq l_u\) 时才能从 \(u\) 跳到 \(v\)。\(\forall 1 < i \leq n\),求从点 \(i\) 跳到点 \(1\) 的最小代价。

\(n \leq 2 \times 10^5\)

思路

点分治 + 斜率优化 dp.

观察转移的代价代价,可以写成 \((\operatorname{depth}(u) - \operatorname{depth}(v))p_u + q_u + f_v\) 的形式,拆开得到:

\(\operatorname{depth}(u) p_u - \operatorname{depth}(v)p_u + q_u\)

满足斜率优化的形式,考虑从点 \(i\) 转移优于从点 \(j\) 转移的条件:

\(\operatorname{depth}(u) p_u - \operatorname{depth}(i) p_u + q_u + f_i \leq \operatorname{depth}(u) p_u - \operatorname{depth}(j)p_u + q_u + f_j\)

即 \(f_i - \operatorname{depth}(i) p_u \leq f_j - \operatorname{depth}(j)p_u\)

移项得到 \(f_i - f_j \leq \operatorname{depth}(i) p_u - \operatorname{depth}(j)p_u\)

即 \(\frac{f_i - f_j}{\operatorname{depth}(i) - \operatorname{depth}(j)} \leq p_u\)

但是这里的斜率优化是在树上做的,随 dfs 回溯复杂度摊下来是假的。

于是可以考虑用点分治优化。

点分治考虑的是每次划分出子树重心,那么转移的贡献可以分成两部分:

  1. 当前子树除重心所在子树之外的部分 -> 其自身

  2. 当前子树除重心所在子树之外的部分 -> 重心所在子树

那么可以考虑在点分治的时候维护第二类贡献。

但是问题在于每个点可以转移到范围不固定也不单调,比较难搞。

这里可以考虑在点分每层的时候把所有结点按照可以转移的范围从小到大排序,于是就不需要考虑撤销操作。

那么现在只需要考虑维护加入点的贡献即可,这里直接上果的丹钓战。

注意 \(x\) 坐标不单调,要在凸包上二分最优的转移位置。

代码

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

const int maxn = 2e5 + 5;
const ll inf = 1e18;

struct Point
{
    ll x, y;

    Point() : x(), y() {}
    Point(ll _x, ll _y) : x(_x), y(_y) {}
    Point operator - (Point rhs) { return Point(x - rhs.x, y - rhs.y); }
} stk1[maxn], stk2[maxn];

int n, t;
int top1, top2, rt, tot;
int fa[maxn], mx[maxn], sz[maxn];
ll d[maxn], dp[maxn];
ll s[maxn], l[maxn], p[maxn], q[maxn];
bool vis[maxn];
double sl[maxn];
vector<int> g[maxn];

void dfs1(int u)
{
    sz[u] = 1, mx[u] = 0;
    for (int v : g[u])
    {
        if (!vis[v])
        {
            dfs1(v);
            sz[u] += sz[v];
            mx[u] = max(mx[u], sz[v]);
        }
    }
    if ((rt == -1) || max(mx[u], tot - sz[u]) < max(mx[rt], tot - sz[rt])) rt = u;
}

void dfs2(int u)
{
    if (l[u] - d[u] > 0) stk1[++top1] = Point(l[u] - d[u], u);
    for (int v : g[u])
        if (!vis[v]) d[v] = d[u] + s[v], dfs2(v);
}

bool cmp(Point a, Point b) { return (a.x < b.x); }

double slope(Point a, Point b) { return (double)(a.y - b.y) / (a.x - b.x); }

void insert(Point a)
{
    while ((top2 > 1) && (slope(a, stk2[top2]) <= sl[top2])) top2--;
    stk2[++top2] = a;
    sl[top2] = (top2 > 1 ? slope(stk2[top2], stk2[top2 - 1]) : -inf);
}

ll query(ll k)
{
    int l = 1, r = top2;
    ll res = 0;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (sl[mid] <= k) res = stk2[mid].y - stk2[mid].x * k, l = mid + 1;
        else r = mid - 1;
    }
    return res;
}

void solve(int u)
{
    rt = -1;
    dfs1(u);
    vis[rt] = true;
    int nd = rt;
    if (nd != u) tot -= sz[nd], solve(u);
    int v = nd;
    ll dis = 0;
    top1 = top2 = d[nd] = 0, dfs2(nd);
    sort(stk1 + 1, stk1 + top1 + 1, cmp);
    for (int i = 1; i <= top1; i++)
    {
        ll lim = stk1[i].x;
        int w = stk1[i].y;
        while ((v != fa[u]) && (dis + s[v] <= lim) && fa[v])
        {
            dis += s[v];
            insert(Point(dis, dp[fa[v]]));
            v = fa[v];
        }
        if (top2) dp[w] = min(dp[w], query(-p[w]) + d[w] * p[w] + q[w]);
    }
    for (int to : g[nd])
        if (!vis[to]) tot = sz[to], solve(to);
}

int main()
{
    scanf("%d%d", &n, &t);
    for (int i = 2; i <= n; i++)
    {
        scanf("%d%lld%lld%lld%lld", &fa[i], &s[i], &p[i], &q[i], &l[i]);
        g[fa[i]].push_back(i);
        dp[i] = inf;
    }
    tot = n;
    vis[0] = true;
    solve(1);
    for (int i = 2; i <= n; i++) printf("%lld\n", dp[i]);
    return 0;
}

标签:Point,int,题解,ll,operatorname,NOI2014,depth,maxn,P2305
From: https://www.cnblogs.com/lingspace/p/p2305.html

相关文章

  • BalticOI 2004 Sequence 题解
    题目链接在这里~对于序列\(\{a\}\),把每一个\(a_i\)减去一个\(i\),得到\(\{a'\}\)序列\(\{b\}\)同理。因为\(b_1<b_2<...<b_n\),故\(b_1'\leqslantb_2'\leqslant...\leqs......
  • ATC简单题解(不定时更新
    ABC129前三题略D.lamp虽然数据范围不大,但也没法暴力check,可以考虑分别维护每行(每列)障碍物的纵(横)坐标,可以考虑到插入std::vector中,然后对于每一个点查找横竖方向上的......
  • CF893D Credit Card 题解
    简要题意:你有一张信用卡,\(n\)天有\(n\)个操作,每次操作给定一个\(x\),如果\(x\)是\(0\)那么银行会查询信用卡里的金额,要保证金额是非负数;否则你卡里的金额会变化\(x......
  • 安徽农业大学寒假训练赛1题解
    D#include<bits/stdc++.h>usingnamespacestd;charg[10][10];intmain(){for(inti=1;i<=5;i++)scanf("%s",g[i]+1);//这样可以保证下标都从1......
  • 题解 : Luogu P2197 【模板】nim 游戏
    题目链接:link结论如果$a_1\oplusa_2\oplus...\oplusa_n\not=0$,则先手必胜证明操作到最后时,每堆石子数都是\(0\),\(0\oplus0\oplus...\oplus0=0......
  • Starling常见问题解决办法
    ​​Starling常见问题解决办法​​来自:​​智慧+毅力=无所不能​​ 1、Android设备上阻止用户按下后退后的行为侦听按键事件//阻止后退行为view.stage.addEventL......
  • JSOI2009 题解
    Count二维树状数组板子题,开\(c\)个二维树状数组即可过。可以通过离线对每个权值单独操作做到只开一个二维树状数组。如果空间要求更紧的话可以cdq分治做到只开一个......
  • unity和VS2019联调问题解决
    以前使用VS2015和17的时候联调的时候是可以附加到unity进行联调的,今天用的2019发现不可以了。研究了一下是少装了一个插件。装上插件就解决了。过程如下:当前使用VS版本2019......
  • 洛谷 p5536 题解
    题目链接:https://www.luogu.com.cn/problem/P5536此题为树的dfs的一个应用。思路树dfs时,可以计算每个点的深度。如图所示可以多次dfs,从而找到不同的信息。代码......
  • CF513F2 题解
    题意传送门有\(a+b+1\)个会动的棋子,在一个大小为\(n\timesm\)的棋盘上,棋盘上有一些点有障碍。棋子中,有\(a\)个红色棋子,\(b\)个蓝色棋子,和\(1\)个既能当作红棋......