:::info[Description] Link. :::
:::infoSolution （可能是第一次写斜率优化）
记 表示从 号点移动到 号点所需花费的最小代价是多少。容易得到重要贪心结论： 点移动过程中一定只会一直沿着从其出发到根结点的路径移动。因此容易想到维护 表示从 号点到 号点的简单路径的长度是多少，则此时对于有祖孙关系的 两个点，其在树上的简单路径距离就是 。容易列出 时间复杂度的 dp 转移方程：
简单变形后可得：
这个式子看上去就非常能斜率优化。对相邻的两个满足条件的转移点 比较从其转移而来可得的贡献：。因为所有合法转移点都必然是从 开始到 号结点的简单路径上的一段前缀，因此这里认为 在树上是 结点的祖先，即 ，后面只需要利用 性质即可。此时把 看作是 轴坐标， 看作是 轴坐标，则决策 优于决策 当且仅当 即 和 两个点之间组成的线段斜率严格大于 。
此时考虑套路的用单调栈来维护一个下凸壳作为合法转移点，此时对每个 在下凸壳上二分即可单 时间复杂度找出合适的决策点。
然而此时并不能直接这样维护单调栈，因为在栈中弹出的决策点还有可能在其他点被弹栈时再次成为合法且可能最优的决策点。因此考虑用树状数组通过维护若干个区间内单调栈的信息来得出某一个后缀内单调栈的信息做到 时间复杂度解决问题。特殊的，因为单调栈需要在树上动态维护，因此在支持插入操作的过程中还需要支持回溯（即回滚上一次入栈）操作，而直接暴力回滚时间复杂度可能会退化到单次 。考虑维护之前每一次操作前栈顶指针的位置和操作后栈顶位置在操作前的值，其余弹栈的位置的信息看作冗余信息即可做到 撤销入栈操作。
该算法总时间复杂度为 ，可以通过该题。 :::
:::success[Code]
namespace lowspeed_song {
inline void init() {
}
int dep[N], w[N], p[N], q[N], lim[N], dis[N], pd[N], n, ty, f[N];
struct Convex_Hull {
vector<pair<int, int>> stk;
vector<int> a;
int top = 0;
inline int bad(int x, int y, int z) { return (i128)(f[y] - f[x]) * (dis[z] - dis[y]) >= (i128)(f[z] - f[y]) * (dis[y] - dis[x]); }
inline void push(int x) {
int old = top, pos = top, l = 1, r = top - 1;
while (l <= r) {
int mid = l + r >> 1;
if (bad(a[mid - 1], a[mid], x)) pos = mid, r = mid - 1;
else l = mid + 1;
} stk.emplace_back(old, (pos < a.size()) ? a[pos] : 0);
if (pos == a.size()) a.emplace_back(x);
else a[pos] = x;
top = pos + 1;
}
inline void pop() {
auto [oldtop, oldval] = stk.back(); stk.pop_back();
a[top - 1] = oldval, top = oldtop;
}
inline int qry(int x) {
if (!top) return inf;
int l = 0, r = top - 2, best = 0;
while (l <= r) {
int mid = l + r >> 1;
if ((i128)(f[a[mid + 1]] - f[a[mid]]) <= (i128)x * (dis[a[mid + 1]] - dis[a[mid]])) l = mid + 1, best = mid + 1;
else r = mid - 1;
} return f[a[best]] - dis[a[best]] * x;
}
};
struct BIT {
Convex_Hull tree[N];
inline void add(int x, int v) { for (x = n - x; x <= n; x += (x &- x)) tree[x].push(v); }
inline void del(int x) { for (x = n - x; x <= n; x += (x &- x)) tree[x].pop(); }
inline int qry(int x, int v) {
int res = inf;
for (x = n - x; x; x -= (x &- x)) res = min(res, tree[x].qry(v));
return res;
}
} fwt;
vector<int> adj[N];
inline void sol() {
cin >> n >> ty;
for (int i = 2; i <= n; ++i) {
int fa; cin >> fa;
cin >> w[i] >> p[i] >> q[i] >> lim[i];
adj[fa].emplace_back(i);
} fwt.add(0, 1);
vector<pair<int, int>> stk = {{1, 0}};
while (stk.size()) {
int u = stk.back().first, &i = stk.back().second;
if (i == adj[u].size()) {
if (u != 1) fwt.del(dep[u]);
stk.pop_back();
} else {
int v = adj[u][i++];
dep[v] = dep[u] + 1, dis[v] = dis[u] + w[v], pd[dep[v]] = dis[v];
f[v] = dis[v] * p[v] + q[v] + fwt.qry(lower_bound(pd, pd + dep[v], dis[v] - lim[v]) - pd, p[v]);
fwt.add(dep[v], v), stk.emplace_back(v, 0);
}
} for (int i = 2; i <= n; ++i) cout << f[i] << '\n';
}
} // namespace lowspeed_song:::
难度：黑-
鲜活指数：7
喜欢的话，留下你的评论吧～