BZOJ3672: [Noi2014]购票【CDQ分治】【点分治】【斜率优化DP】

Description

今年夏天,NOI在SZ市迎来了她30周岁的生日。来自全国 n 个城市的OIer们都会从各地出发,到SZ市参加这次盛会。

全国的城市构成了一棵以SZ市为根的有根树,每个城市与它的父亲用道路连接。为了方便起见,我们将全国的 n 个城市用 1 到 n 的整数编号。其中SZ市的编号为 1。对于除SZ市之外的任意一个城市 v,我们给出了它在这棵树上的父亲城市 fv 以及到父亲城市道路的长度 sv。

从城市 v 前往SZ市的方法为:选择城市 v 的一个祖先 a,支付购票的费用,乘坐交通工具到达 a。再选择城市 a 的一个祖先 b,支付费用并到达 b。以此类推,直至到达SZ市。

对于任意一个城市 v,我们会给出一个交通工具的距离限制 lv。对于城市 v 的祖先 a,只有当它们之间所有道路的总长度不超过 lv 时,从城市 v 才可以通过一次购票到达城市 a,否则不能通过一次购票到达。对于每个城市 v,我们还会给出两个非负整数 pv,qv 作为票价参数。若城市 v 到城市 a 所有道路的总长度为 d,那么从城市 v 到城市 a 购买的票价为 dpv+qv。

每个城市的OIer都希望自己到达SZ市时,用于购票的总资金最少。你的任务就是,告诉每个城市的OIer他们所花的最少资金是多少。

Input

第 1 行包含2个非负整数 n,t,分别表示城市的个数和数据类型(其意义将在后面提到)。输入文件的第 2 到 n 行,每行描述一个除SZ之外的城市。其中第 v 行包含 5 个非负整数 f_v,s_v,p_v,q_v,l_v,分别表示城市 v 的父亲城市,它到父亲城市道路的长度,票价的两个参数和距离限制。请注意:输入不包含编号为 1 的SZ市,第 2 行到第 n 行分别描述的是城市 2 到城市 n。

Output

输出包含 n-1 行,每行包含一个整数。其中第 v 行表示从城市 v+1 出发,到达SZ市最少的购票费用。同样请注意:输出不包含编号为 1 的SZ市。

Sample Input

7 3

1 2 20 0 3

1 5 10 100 5

2 4 10 10 10

2 9 1 100 10

3 5 20 100 10

4 4 20 0 10

Sample Output

40

150

0

149

300

150

HINT

BZOJ3672: [Noi2014]购票【CDQ分治】【点分治】【斜率优化DP】

对于所有测试数据,保证 0≤pv≤106,0≤qv≤1012,1≤fv<v;保证 0<sv≤lv≤2×1011,且任意城市到SZ市的总路程长度不超过 2×1011。

输入的 t 表示数据类型,0≤t<4,其中:

当 t=0 或 2 时,对输入的所有城市 v,都有 fv=v-1,即所有城市构成一个以SZ市为终点的链;

当 t=0 或 1 时,对输入的所有城市 v,都有 lv=2×1011,即没有移动的距离限制,每个城市都能到达它的所有祖先;

当 t=3 时,数据没有特殊性质。

n=2×10^5


思路

经典好题吧

知识点很全

首先考虑在一条链上怎么做?

斜率优化是一眼的

但是在树上怎么办?

我们要用一个节点的所有父亲来更新这个节点的dp值

考虑下分治算法来优化这个过程

在斜率优化的处理方式中有一种经典操作叫cdq分治

就是先处理一部分然后用这一部分更新剩下的部分,然后再递归处理剩下的部分

这里我们把问题模型抽象出来

如果把树划分成几个部分的话,我们考虑一个事情,就是说用来更新的祖先是一条链,可以更新到的儿子是一个子树

我们把祖先的链当成前一个部分,儿子当做另一个部分

也就是说我们先处理出前一个部分的所有信息,然后再用来更新儿子

考虑分治的过程

当前分治的树根是u,分治中心是rt

那么显然\([rt,u]\)这条链上的信息我们需要先处理出来

所以我们优先递归除了rt子树外的所有节点

然后再把\([rt,u]\)这一条链提出来更新rt的子树

注意因为有一个最大长度限制

所以我们进行更新的时候一定要注意把子树节点按照一定顺序排好,使得可以更新每一个节点的祖先数量单调不降

然后就对祖先维护凸壳就好了


注意一下点积不要爆longlong,用longdouble

还有找重心的时候如果当前节点siz是1需要特判一下不能作为重心


#include<bits/stdc++.h>

using namespace std;

typedef long double ld;
typedef long long ll; ll read() {
ll res = 0, w = 1; char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') c = getchar(), w = -1;
while (isdigit(c)) res = (res << 1) + (res << 3) + c - '0', c = getchar();
return w * res;
} const ll INF_of_ll = 1e18;
const ll N = 2e5 + 10; struct Node {
ll id, val;
Node() {}
Node(ll id, ll val): id(id), val(val) {}
} rque[N]; bool operator < (const Node &a, const Node &b) {
return a.val > b.val;
} struct Vector {
ll x, y;
Vector() {}
Vector(ll x, ll y): x(x), y(y) {}
} lque[N]; Vector operator - (const Vector &a, const Vector &b) {
return Vector(a.x - b.x, a.y - b.y);
} ld operator * (const Vector &a, const Vector &b) {
return (ld) a.x * b.y - (ld) a.y * b.x;
} struct Edge {
ll v, w, nxt;
} E[N << 1]; ll topl, topr;
ll head[N], tot = 0;
ll n, prt[N], p[N], q[N], limit[N], dp[N];
ll siz[N], dis[N], F[N], vis[N], siz_all; void addedge(ll u, ll v, ll w) {
E[++tot] = (Edge) {v, w, head[u]};
head[u] = tot;
} void getsiz(ll u) {
siz[u] = 1;
for (ll i = head[u]; i; i = E[i].nxt) {
ll v = E[i].v;
if (vis[v]) continue;
dis[v] = dis[u] + E[i].w;
getsiz(v);
siz[u] += siz[v];
}
} void getrt(ll u, ll &rt) {
F[u] = siz_all - siz[u];
for (ll i = head[u]; i; i = E[i].nxt) {
ll v = E[i].v;
if (vis[v]) continue;
getrt(v, rt);
F[u] = max(F[u], siz[v]);
}
if (F[u] < F[rt] && siz[u] > 1) rt = u;
} void dfs(ll u) {
rque[++topr] = (Node) {u, dis[u] - limit[u]};
for (ll i = head[u]; i; i = E[i].nxt)
if (!vis[E[i].v]) dfs(E[i].v);
} ll calc(ll v, Vector u) {
return u.y + (dis[v] - u.x) * p[v] + q[v];
} void solve(ll u, ll cursiz) {
if (cursiz == 1) return;
ll rt = 0;
getsiz(u);
F[rt] = siz_all = cursiz;
getrt(u, rt);
for (ll i = head[rt]; i; i = E[i].nxt)
vis[E[i].v] = 1;
solve(u, cursiz - siz[rt] + 1);
topl = topr = 0;
for (ll i = head[rt]; i; i = E[i].nxt)
dfs(E[i].v);
sort(rque + 1, rque + topr + 1);
ll cur = rt;
lque[0] = Vector(dis[rt] + 1, INF_of_ll);
for (ll i = 1; i <= topr; i++) {
while (cur != prt[u] && dis[cur] >= rque[i].val) {
Vector now(dis[cur], dp[cur]);
while (topl > 1 && (lque[topl] - lque[topl - 1]) * (now - lque[topl - 1]) > 0.0) topl--;
lque[++topl] = now;
cur = prt[cur];
}
if (topl) {
ll l = 1, r = topl, res = 1, now = rque[i].id;
while (l <= r) {
ll mid = (l + r) >> 1;
if (calc(now, lque[mid]) <= calc(now, lque[mid - 1])) res = mid, l = mid + 1;
else r = mid - 1;
}
dp[now] = min(dp[now], calc(now, lque[res]));
}
}
for (ll i = head[rt]; i; i = E[i].nxt)
solve(E[i].v, siz[E[i].v]);
} int main() {
#ifdef dream_maker
freopen("input.txt", "r", stdin);
#endif
n = read();
ll typ = read();
for (ll i = 2; i <= n; i++) {
prt[i] = read();
ll w = read();
addedge(prt[i], i, w);
p[i] = read();
q[i] = read();
limit[i] = read();
dp[i] = INF_of_ll;
}
solve(1, n);
for (ll i = 2; i <= n; i++)
printf("%lld\n", dp[i]);
return 0;
}
上一篇:Mysql 5.5 replication 多数据库主从备份Master-Slave配置总结


下一篇:c# 值传递 引用传递