考场上只想到暴力。
如果只是一条链的话怎么乱搞一搞？
如果没有深度限制的话简单的斜率优化+链剖就行了。
有深度限制就把hull扔到线段树里用可持久化栈来维护一下。DFS的时候塞进线段树里，然后完了再扔出来。总的复杂度O(n*log^2(n))，
代码也不怎么复杂。
#include <cstdio>
#include <cctype>
#include <memory.h>
#include <vector>
#include <algorithm>
using namespace std;
struct edge {
int t;
edge* next;
};
typedef long long qw;
typedef long double exf;
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define _l (qw)
#define readInt(_s_) {\
int _d_;\
_s_ = 0;\
while (!isdigit(_d_ = getchar()));\
while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\
}
struct oper {
int p, v, t;
oper(int p0 = 0, int v0 = 0, int t0 = 0) {
p = p0, v = v0, t = t0;
}
};
struct phull {
int *s, t;
vector <oper> r;
};
struct seg {
int l, r;
phull d;
seg *ls, *rs;
};
const int maxn = 200009;
const qw inf = 0x3f3f3f3f3f3f3f3fLL;
const exf eps = 1e-8;
qw d[maxn], k[maxn], b[maxn], dl[maxn], f[maxn];
int n, fa[maxn], stc[maxn];
edge *head[maxn], *ep;
seg *rt, *sp;
inline exf getK(int a, int b) {
return ((exf)f[b] - f[a]) / ((exf)d[b] - d[a]);
}
inline void addEdge(int u, int v) {
ep-> t = v;
ep-> next = head[u];
head[u] = ep ++;
}
#define mid(p) ((p->l+p->r)>>1)
void phIns(phull& h, int v0) {
if (!h. t) {
h. r. push_back(oper(1, 0, 0));
h. s[h. t = 1] = v0;
}
else if (h. t == 1) {
h. r. push_back(oper(2, 0, 1));
h. s[h. t = 2] = v0;
}
else {
int l = 2, r = h. t;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (getK(h. s[mid - 1], h. s[mid]) > getK(h. s[mid - 1], v0) + eps)
r = mid - 1;
else
l = mid;
}
if (l > 2 || getK(h. s[1], h. s[2]) <= getK(h. s[1], v0))
++ l;
h. r. push_back(oper(l, h. s[l], h. t));
h. s[h. t = l] = v0;
}
}
void phCancel(phull& h) {
if (h. r. empty())
return;
oper o = *h. r. rbegin();
h. r. pop_back();
h. s[o. p] = o. v;
h. t = o. t;
}
qw phQry(phull& h, int i) {
int l = 1, r = h. t - 1;
if (!h. t)
return inf;
while (l < r) {
int mid = (l + r) >> 1;
if (getK(h. s[mid], h. s[mid + 1]) + eps < k[i])
l = mid + 1;
else
r = mid;
}
if (l == h. t - 1 && getK(h. s[l], h. s[l + 1]) + eps < k[i])
++ l;
return f[h. s[l]] + (d[i] - d[h. s[l]]) * k[i] + b[i];
}
seg *sgtBuild(int l, int r) {
seg *p = sp ++;
p-> d. s = new int[r - l + 3];
p-> d. t = 0;
p-> l = l;
p-> r = r;
if (l + 1 < r) {
p-> ls = sgtBuild(l, mid(p));
p-> rs = sgtBuild(mid(p), r);
}
return p;
}
void sgtChg(seg* p, int p0, int v0) {
if (v0 == -1)
phCancel(p-> d);
else
phIns(p-> d, v0);
if (p-> l + 1 < p-> r) {
if (p0 < mid(p))
sgtChg(p-> ls, p0, v0);
else
sgtChg(p-> rs, p0, v0);
}
}
qw sgtQry(seg* p, int l, int r, int v0) {
if (l >= r)
return inf;
else if (l == p-> l && r == p-> r)
return phQry(p-> d, v0);
else if (r <= mid(p))
return sgtQry(p-> ls, l, r, v0);
else if (l >= mid(p))
return sgtQry(p-> rs, l, r, v0);
else
return min(sgtQry(p-> ls, l, mid(p), v0), sgtQry(p-> rs, mid(p), r, v0));
}
qw getAns(int p, int d0) {
int l = 1, r = d0;
while (l < r) {
int mid = (l + r) >> 1;
if (d[p] - d[stc[mid]] > dl[p])
l = mid + 1;
else
r = mid;
}
return sgtQry(rt, l, d0 + 1, p);
}
void dfs(int p, int d0) {
if (p > 1)
f[p] = getAns(p, d0 - 1);
sgtChg(rt, d0, p);
stc[d0] = p;
for (edge* e = head[p]; e; e = e-> next)
dfs(e-> t, d0 + 1);
sgtChg(rt, d0, -1);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("ticket.in", "r", stdin);
freopen("ticket.out", "w", stdout);
#endif
memset(head, 0, sizeof(head));
ep = new edge[maxn];
qw tmp;
readInt(n);
readInt(tmp);
sp = new seg[maxn * 3];
rt = sgtBuild(1, n + 1);
d[1] = 0;
f[1] = 0;
for (int i = 2; i <= n; ++ i) {
readInt(fa[i]);
addEdge(fa[i], i);
readInt(tmp);
d[i] = d[fa[i]] + tmp;
readInt(k[i]);
readInt(b[i]);
readInt(dl[i]);
}
dfs(1, 1);
for (int i = 2; i <= n; ++ i)
printf(lld "\n", f[i]);
}