$ \color{#0066ff}{ 题目描述 }$
C 国拥有一张四通八达的高速公路网树, 其中有 n 个城市, 城市之间由一共 n-1 条高速公路连接. 除了首都 1 号城市, 每个城市都有一家本地的客运公司, 可以发车前往全国各地, 有若干条高速公路连向其他城市, 这是一个树型结构, 1 号城市 (首都) 为根. 假设有一个人要从 i 号城市坐车出发前往 j 号城市, 那么他要花费 Pi*(i 城市到 j 城市的距离)+Qi 元. 由于距离首都越远, 国家的监管就越松, 所以距离首都越远, 客运公司的 Pi(单位距离价格)越大, 形式化的说, 如果把高速路网看成一棵以首都为根的有根树, i 号城市是 j 号城市的某个祖先, 那么一定存在 Pi<=Pj.
大宁成为了国家统计局的调查人员, 他需要对现在的高速路网进行一次调查, 了解从其他每一个城市到达首都 1 号城市所花费的金钱(路径必须是简单路径).
因为有非常多转车 (或不转车) 的抵达首都的方法, 所以人工计算这个结果是十分复杂的. 大宁非常的懒, 所以请你编写一个程序解决它.
\(\color{#0066ff}{输入格式}\)
第 1 行包含 1 个非负整数 n, 表示城市的个数.
第 2 到 n 行, 每行描述一个除首都之外的城市. 其中第 i 行包含 4 个非负整数 Fi,Si,Pi,Qi, 分别表示 i 号城市的父亲城市, 它到父亲城市高速公路的长度, 以及乘车价格的两个参数.
\(\color{#0066ff}{输出格式}\)
输出包含 n-1 行, 每行包含一个整数.
其中第 i 行表示从 i+1 号城市 出发, 到达首都最少的乘车费用.
- \(\color{
- #0066ff
- }{
- 输入样例
- }\)
- 6
- 1 9 3 0
- 1 17 1 9
- 1 1 1 6
- 4 13 2 15
- 4 9 2 4
- \(\color{
- #0066ff
- }{
- 输出样例
- }\)
- 27 26 7 43 24
- \(\color{
- #0066ff
- }{
- 数据范围与提示
- }\)
对于前 40% 的数据 1<=n<=1000.
对于另外 20% 的数据 满足从第 i(i≠1)个城市出发的高速公路连向第 i-1 个城市.
对于所有的数据 1<=n<=1000000,0<=Pi,Qi<=2^31-1, 保证结果不会大于 2^63-1.
\(\color{#0066ff}{题解}\)
不难想到 DP, 设 \(f[i]\)为从 i 到根的答案, 转移也很好想
\(f[i] =min(f[i],f[j]+(dis[i])-dis[j])*p[i]+q[i])\)
但是这样转移是 \(O(n^2)\)的, 显然过不了啊
我们考虑斜率优化
如果 x 比 y 优秀, 即 \(f[x]+(dis[i]-dis[x])*p[i]+q[i]<f[y]+(dis[i]-dis[y])*p[i]+q[i]\)
化简之后是 \(p[i]<\frac{f[x]-f[y]}{dis[x]-dis[y]}\)
这样就能斜率优化了, 用单调队列维护一个下凸包
但是, 这是优化的树形 DP 啊, 在一棵子树内的决策会影响到另一棵子树!
我们考虑每次转移单调队列的变化, 看能不能搞点什么
可以发现, 每次 head 仅仅是移动, 其中元素是不变的(祖先链不变)
tail 呢? 每次移动后只会修改一个值!
所以我们可以记录一下每个点的 head 和 tail, 还有修改的元素位置和编号, 这样就可以快速回溯
但是这样每个点会入队多次, 上界依然是 \(O(n^2)\)
又因为元素是不变的, 所以, 我们考虑二分来优化这个过程, 每次二分两次, 找到转移点和修改点即可
- #include<bits/stdc++.h>
- #define LL long long
- LL in() {
- char ch; LL x = 0, f = 1;
- while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
- for(x = ch ^ 48; isdigit(ch = getchar()); x = (x <<1) + (x << 3) + (ch ^ 48));
- return x * f;
- }
- const int maxn = 1e6 + 100;
- LL dep[maxn], f[maxn];
- LL p[maxn], q[maxn];
- int st[maxn], head, tail;
- int n;
- struct node {
- int to, dis;
- node *nxt;
- node(int to = 0, int dis = 0, node *nxt = NULL): to(to), dis(dis), nxt(nxt) {}
- }*h[maxn];
- void add(int from, int to, int dis) { h[from] = new node(to, dis, h[from]); }
- void dfs(int x) { for(node *i = h[x]; i; i = i->nxt) dep[i->to] = dep[x] + i->dis, dfs(i->to); }
- double K(int x, int y) { return (double)(f[x] - f[y]) / (double)(dep[x] - dep[y]); }
- void work(int x) {
- int nowhead = head, nowtail = tail;
- int l = head, r = tail - 1, ans = -1;
- while(l <= r) {
- int mid = (l + r)>> 1;
- if(p[x] <= K(st[mid], st[mid + 1])) ans = mid, r = mid - 1;
- else l = mid + 1;
- }
- if(~ans) head = ans;
- else head = tail;
- f[x] = f[st[head]] + (dep[x] - dep[st[head]]) * p[x] + q[x];
- l = head, r = tail - 1, ans = -1;
- while(l <= r) {
- int mid = (l + r)>> 1;
- if(K(st[mid], st[mid + 1]) <K(st[mid + 1], x)) ans = mid, l = mid + 1;
- else r = mid - 1;
- }
- if(~ans) tail = ans + 1;
- else tail = head;
- int now = st[++tail];
- st[tail] = x;
- for(node *i = h[x]; i; i = i->nxt) work(i->to);
- head = nowhead, st[tail] = now, tail = nowtail;
- }
- int main() {
- n = in();
- int x, y;
- for(int i = 2; i <= n; i++) {
- x = in(), y = in();
- add(x, i, y);
- p[i] = in(), q[i] = in();
- }
- dfs(1);
- for(node *i = h[1]; i; i = i->nxt) st[head = tail = 1] = 1, work(i->to);
- for(int i = 2; i <= n; i++) printf("%lld\n", f[i]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2987374.html