LOJ 2249: 洛谷 P2305: 「NOI2014」购票
题目传送门:LOJ #2249。
题意简述:
有一棵以 \(1\) 号节点为根节点的带边权的树。
除了 \(1\) 号节点的所有节点上都有人需要坐车到达 \(1\) 号节点。
除了 \(1\) 号节点,每个节点都有 \(5\) 个参数 \(f_u,s_u,p_u,q_u,l_u\)。
\(f_u\) 表示 \(u\) 号点的父亲,\(s_u\) 表示 \(u\) 号点与父亲之间的边的权值,\(p,q,l\) 为车票参数。
定义两个节点 \(u\) 和 \(v\) 之间的距离 \(dis_{u,v}\) 为 \(u\) 和 \(v\) 在树上的简单路径上的边权之和。
从一个节点 \(u\),可以坐车到达节点 \(v\) 当且仅当 \(dis_{u,v}\le l_u\),且需要花费 \(dis_{u,v}\times p_u+q_u\) 的代价。
问除了 \(1\) 号节点的每个节点坐车到 \(1\) 号节点需要花费的最小总代价。
\(1\le n\le 2\times 10^5\),保证输入的所有数都是非负整数,\(l_u\ge s_u\),保证答案在 long long
范围内。
题解:
考虑树形 DP,令 \(\mathrm{f}[u]\) 为 \(u\) 到 \(1\) 的最小总代价,\(\mathrm{dis}[u]\) 为 \(1\) 号节点到 \(u\) 号节点的距离。
则有 \(\mathrm{f}[u]=\min\limits_{\substack{v\in anc_u\\\mathrm{dis}[u]-\mathrm{dis}[v]\le l_u}}(\mathrm{f}[v]+(\mathrm{dis}[u]-\mathrm{dis}[v])\times p_u+q_u)\)。
令 \(b_u=\mathrm{dis}[u]\times p_u+q_u\),则有:
\]
观察式子,发现 \(v\) 必须是紧接着 \(u\) 往上一段连续的祖先,而转移的方式是简单的加权值取 \(\min\)。
这提示我们考虑斜率优化,考虑两个合法转移点 \(j\) 和 \(k\),比较 \(j\) 和 \(k\) 转移的优劣:
\]
发现已经有了斜率的表达式,\(x\) 坐标是 \(\mathrm{dis}\),\(y\) 坐标是 \(\mathrm{f}\)。假设 \(\mathrm{dis}[j]<\mathrm{dis}[k]\),则决策 \(j\) 比 \(k\) 优当且仅当:
\]
即点 \((\mathrm{dis}[j],\mathrm{f}[j])\) 和点 \((\mathrm{dis}[k],\mathrm{f}[k])\) 之间的线段的斜率大于 \(p_u\)。
所以我们需要用单调栈维护一个合法点的下凸壳,这样可以根据不同的 \(p_u\) 在凸壳上二分得到决策点。
但是这样有一个问题,我们知道合法的决策点是 \(u\) 的近几层祖先,即 \(u\) 到祖先的链上 \(\mathrm{dis}\) 较大的节点,它们对应的点也是靠右的。
考虑这张图,假设 A 点是非法转移点,而 B、C、D 都是合法转移点,此时维护的凸壳并不包含 B,然而 B 可能是最优决策点。
也就是说,我们需要考虑一段后缀中的最优转移点,然而我们又不能维护所有后缀的凸壳,应该怎么办呢?
有一个解决方法:维护一些区间中的凸壳,查询时选择一些区间的并恰好等于需要的后缀,在每个区间内分别查询最优决策并更新。
这提示我们使用树状数组维护后缀信息,也就是树状数组套单调栈。
这样花费的空间是 \(\Theta(n\log n)\) 的,修改时间 \(\mathcal{O}(\log n)\),查询时间 \(\mathcal{O}(\log^2 n)\)。
还有最后一个问题,需要处理的不是序列上而是树上的转移,这并不难实现,我们维护可撤销单调栈,在回溯的时候撤销这次操作即可。
关于可撤销单调栈,考虑单调栈的每一次操作只会更改栈顶指针以及栈顶位置的值,我们维护历史每一次操作原先的栈顶指针以及栈顶位置原来的值即可实现撤销操作,这样插入和撤销均是 \(\Theta(1)\) 的。
#include <cstdio>
#include <vector>
#include <algorithm>
typedef long long LL;
const int MN = 200005;
const int MS = 2100005;
const LL Inf = 0x7fffffffffffffff;
int N, faz[MN];
std::vector<int> G[MN];
LL wgh[MN], dep[MN], dis[MN], p[MN], q[MN], b[MN], len[MN];
LL stds[MN], tds;
LL f[MN], *X = dis, *Y = f;
inline double Slope(int i, int j) {
return X[i] == X[j] ? 1e60 : (double)(Y[j] - Y[i]) / (X[j] - X[i]);
}
int stkp[MS], valp[MS], tpp[MS];
int *istk[MN], *ival[MN], *itp[MN], it[MN];
inline void Push(int id, int u) {
int t = it[id], tp = itp[id][t], *stk = istk[id];
while (tp > 0 && Slope(stk[tp - 1], stk[tp]) >= Slope(stk[tp], u)) --tp;
++t, ival[id][t] = stk[itp[id][t] = ++tp], stk[tp] = u, it[id] = t;
}
inline void Pop(int id) {
istk[id][itp[id][it[id]]] = ival[id][it[id]];
--it[id];
}
inline int chk(int id, LL slp) {
int t = it[id], tp = itp[id][t], *stk = istk[id];
if (!~tp) return -1;
int lb = 0, rb = tp - 1, x = tp, mid;
while (lb <= rb) {
mid = (lb + rb) >> 1;
if (Slope(stk[mid], stk[mid + 1]) <= slp) lb = mid + 1;
else x = mid, rb = mid - 1;
}
return stk[x];
}
inline void PushAll(int i, int u) { for (; i <= N; i += i & -i) Push(i, u); }
inline void PopAll(int i) { for (; i <= N; i += i & -i) Pop(i); }
inline void GetDp(int u) {
f[u] = Inf;
int i = std::lower_bound(stds + 1, stds + tds + 1, dis[u] - len[u]) - stds;
for (i = N - i + 1; i; i -= i & -i) {
int v = chk(i, p[u]);
if (~v) f[u] = std::min(f[u], f[v] - dis[v] * p[u] + b[u]);
}
}
void DFS(int u) {
dep[u] = dep[faz[u]] + 1;
dis[u] = dis[faz[u]] + wgh[u];
stds[++tds] = dis[u];
b[u] = dis[u] * p[u] + q[u];
GetDp(u);
PushAll(N - dep[u], u);
for (auto v : G[u]) DFS(v);
PopAll(N - dep[u]);
--tds;
}
int main() {
scanf("%d%*d", &N);
istk[1] = stkp, itp[1] = tpp, ival[1] = valp, itp[1][it[1] = 0] = -1;
for (int i = 2; i <= N; ++i) {
int lenl = ((i - 1) & (1 - i)) + 1;
istk[i] = istk[i - 1] + lenl;
itp[i] = itp[i - 1] + lenl;
ival[i] = ival[i - 1] + lenl;
itp[i][it[i] = 0] = -1;
}
for (int i = 2; i <= N; ++i) {
scanf("%d%lld%lld%lld%lld", &faz[i], &wgh[i], &p[i], &q[i], &len[i]);
G[faz[i]].push_back(i);
}
PushAll(N, 1), stds[tds = 1] = 0;
for (auto u : G[1]) DFS(u);
for (int i = 2; i <= N; ++i) printf("%lld\n", f[i]);
return 0;
}
最新文章
- redhat7 修改hostname
- while 与do ..while区别
- Moon.Orm常见问题问答FAQ
- VC工程中文件的编译顺序
- Observer,Observable实现观察者模式
- REPEATABLE-READ下批量更新数据的问题
- 图解集合5:不正确地使用HashMap引发死循环及元素丢失
- web.config中customErrors与httpErrors的区别
- php 读取webservice接口
- Java 向Hbase表插入数据报(org.apache.hadoop.hbase.client.HTablePool$PooledHTable cannot be cast to org.apac
- C++模板之Vector与STL初探
- Linux下Git安装、配置
- [国嵌攻略][091][TCP网络程序设计]
- 结巴分词出现AttributeError: &#39;float&#39; object has no attribute &#39;decode&#39;错误
- requirejs官网
- JavaScript之ECMA对象的学习
- 学习Android过程中遇到的问题及解决方法——AS为xutils添加依赖
- machine learning data sets
- Android HttpURLConnection.connect找不到源 HttpURLConnection连接失败 HttpURLConnection.connect IO异常 解决办法
- 基金 、 社保和QFII等机构的重仓股排名评测
热门文章
- akm
- 第四篇——Spring音乐登录界面设计及实现(C#)
- 格式化输出Json对象
- resultMap 表示转换字段后 resultType 表示没&#183;有转换字段
- kvm安装配置
- 认清Android框架 MVC,MVP和MVVM
- 【BZOJ1055】[HAOI2008]玩具取名(动态规划)
- 如何整合Office Web Apps至自己开发的系统(一)
- Objective-C 中的协议(@protocol)和接口(@interface)的区别
- WebSockets Tutorial(教程一)WebSockets简介