題目鏈接

UOJ #7

題解

首先這一定是DP！可以寫出：
\[f[i] = \min_{ancestor\ j} \{f[j] + (d[j] - d[i]) * p[i] + q[i]\}\]
其中\(d[i]\)表示樹上\(i\)的深度。
整理一下式子：
\[f[i] = \min_{ancestor\ j} \{f[j] - d[j] * p[i]\} + d[i] * p[i] + q[i]\]
看起來可以斜率優化？
推一下式子：設\(j < k\)，\(i\)從\(j\)轉移優于從\(k\)轉移：
\[f[j] - d[j] * p[i] < f[k] - d[k] * p[i]\]
\[\frac{f[k] - f[j]}{d[k] - d[j]} > p[i]\]
好的！
所以應該維護一個下凸殼，在上面二分即可。

可是由于限制條件，每個結點\(i\)對應的下凸殼都是不同的，怎么辦呢？

考慮一條鏈的情況：每個\(f[i]\)都是可以由一個區間內的凸包得到。

可以用線段樹維護當前處理完的所有點的凸包，線段樹上每個節點上存儲著一個凸包，查詢的時候相當于在線段樹上區間查詢——如果當前節點所代表的區間完全包含在查詢區間里面，則在這個凸包上二分查詢這個區間可以帶來的最優解，否則遞歸，就可以得到答案了。

現在再考慮把一條鏈上的情況推廣到樹上。

考慮DFS，棧中的節點組成從根到當前節點的一條鏈，如果線段樹維護了這條鏈的信息，則可以像正常序列上的情況一樣求當前點的\(f\)值。
如果當前點DFS完畢出棧時，可以在線段樹上刪除它，就可以不影響復雜度地保證時時刻刻線段樹維護的都是棧中所有節點的信息，就可以求出答案了。

于是引入【可撤銷的凸包】，每次可以【撤銷】——回到上一次插入新節點的操作之前。
怎么實現？當插入一個新節點時，二分它要放到哪個位置，并記錄當前的top和被新節點取代的節點是誰，當撤銷這次插入時，恢復top和被取代的節點即可。這樣插入是\(O(\log n)\)的，撤銷操作是\(O(1)\)的，非常科學 =v=

代碼比想象中好寫（霧

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>
#define space putchar(' ')
#define enter putchar('\n')
using namespace std;
typedef long long ll;
template <class T>
void read(T &x){char c;bool op = 0;while(c = getchar(), c < '0' || c > '9')if(c == '-') op = 1;x = c - '0';while(c = getchar(), c >= '0' && c <= '9')x = x * 10 + c - '0';if(op) x = -x;
}
template <class T>
void write(T x){if(x < 0) putchar('-'), x = -x;if(x >= 10) write(x / 10);putchar('0' + x % 10);
}const int N = 200005;
int n, T, adj[N], nxt[N], fa[N], d_top, id[N];
ll f[N], d[N], p[N], q[N], w[N], lim[N], d_stk[N];
int seg_dep[4*N], pre[N][20], last_top[N][20], top[4*N];
vector <int> stk[4*N];
typedef long double ld;
//pre[i][j]是i號節點在線段樹上第j層加入所屬的凸包中時, "取代"的點的編號, last[i][j]是加入前該凸包的大小
void build(int k, int l, int r){seg_dep[k] = seg_dep[k >> 1] + 1;stk[k].resize(r - l + 3);if(l == r) return;int mid = (l + r) >> 1;build(k << 1, l, mid);build(k << 1 | 1, mid + 1, r);
}
bool cmp1(int i, int j, int k){ // 判斷(i, j, k)是否構成上凸return (ld)(d[j] - d[i]) * (f[k] - f[j]) < (ld)(f[j] - f[i]) * (d[k] - d[j]);
}
int find_pos(int k, int i){ // 在k號單調棧中插入i號點, 應該放在哪個位置if(!top[k]) return 1;int l = 2, r = top[k] + 1, mid; // 找到第一個和i上凸的位置(新來的i應該取代這個位置)while(l < r){mid = (l + r) >> 1;if(cmp1(stk[k][mid - 1], stk[k][mid], i)) r = mid;else l = mid + 1;}return l;
}
void push(int k, int i){int p = find_pos(k, i);last_top[i][seg_dep[k]] = top[k];pre[i][seg_dep[k]] = stk[k][p];top[k] = p;stk[k][p] = i;
}
void rollback(int k){int i = stk[k][top[k]];stk[k][top[k]] = pre[i][seg_dep[k]];top[k] = last_top[i][seg_dep[k]];
}
ll calc(int u, int v){return f[u] + (d[v] - d[u]) * p[v] + q[v];
}
bool cmp2(int i, int j, ll x){ // 判斷i和j構成的斜率是否小于等于xreturn f[j] - f[i] <= (ld) x * (d[j] - d[i]);
}
ll ask(int k, int x){int l = 1, r = top[k];while(l < r){int mid = (l + r) >> 1;if(cmp2(stk[k][mid], stk[k][mid + 1], p[x])) l = mid + 1;else r = mid;}return calc(stk[k][l], x);
}
void insert(int k, int l, int r, int p, bool flag){flag ? push(k, id[p]) : rollback(k);if(l == r) return;int mid = (l + r) >> 1;if(p <= mid) insert(k << 1, l, mid, p, flag);else insert(k << 1 | 1, mid + 1, r, p, flag);
}
ll query(int k, int l, int r, int ql, int qr){if(ql <= l && qr >= r) return ask(k, id[qr + 1]);int mid = (l + r) >> 1;ll ret = 9e18;if(ql <= mid) ret = query(k << 1, l, mid, ql, qr);if(qr > mid) ret = min(ret, query(k << 1 | 1, mid + 1, r, ql, qr));return ret;
}
void dfs(int u){d_stk[++d_top] = d[u] = d[fa[u]] + w[u], id[d_top] = u;if(u != 1){int st = lower_bound(d_stk + 1, d_stk + d_top + 1, d[u] - lim[u]) - d_stk;f[u] = query(1, 1, n, st, d_top - 1);}insert(1, 1, n, d_top, 1);for(int v = adj[u]; v; v = nxt[v]) dfs(v);insert(1, 1, n, d_top, 0);d_top--;
}int main(){read(n), read(T);build(1, 1, n);for(int i = 2; i <= n; i++){read(fa[i]), read(w[i]), read(p[i]), read(q[i]), read(lim[i]);nxt[i] = adj[fa[i]], adj[fa[i]] = i;}dfs(1);for(int i = 2; i <= n; i++)write(f[i]), enter;return 0;
}

轉載于:https://www.cnblogs.com/RabbitHu/p/UOJ7.html

總結

以上是生活随笔為你收集整理的UOJ#7. 【NOI2014】购票 | 线段树 凸包优化DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。