一棵以1为根的n个结点的树, 边带权 (视为距离). 从某点u到达树根的方式: 支付一定代价跳到距离不超过l[u]的祖先v, 再支付一定代价跳到v的某个距离不超过l[v]的祖先w......设一次跳跃的起点为s, 起点终点之间的距离为d, 则这次跳跃的代价为(p[s]d+q[s]), p, q是给定的参数. 求每个点到达树根的最小代价. (0≤p≤10^6, 0≤q≤10^12, 1≤fa[v]<v, 0<v与父亲的距离≤l[v]≤2*10^11, n≤2*10^5) 设点
一个关键而常用 (但我却没想到) 的处理:
花括号内的表达式具有斜率优化的形式. 维护
但现在在树上, 又有距离限制......用可持久化Treap替代Splay维护凸壳? 需要对横坐标打标记? (那时没意识到可以作距离的前缀和) 空间开得下吗?
去瞥了一眼题解, 线段树? 树链剖分?
突然领悟到距离限制会使得凸壳的形态改变......Too young, too simple...Po姐的题解里有一张图, 说明了这种情况.
以为线段树维护凸壳不好写, 可不可以分治呢? CDQ分治? 这是序列......点分治? 这是有根树, 不太好处理吧......
也许可以结合一下, 先点分治, 然后像CDQ分治一样考虑包含根的那棵子树对其他子树的影响......但是没多思考就看题解了, 还真是这样 QAQ 失去一个独立发现正解的机会......思维不要局限啊......可以直接上经典算法它就没必要出到NOI了......
先对包含根的那棵子树递归分治, 然后, 包含根的那棵子树+重心对其他子树的影响这样计算: 将其他子树的结点取出来, 按照lower_bound). 重心必须加入凸壳, 否则永远不会计算它对子树的影响; 可以将它和包含根的子树一起分治 (注意n=2时避免死循环), 也可以暴力计算 (不要像我一样忘了距离限制 QAQ). 最后, 其他子树递归.
树链剖分多一个log, 但代码长度可以做到以下的一半......果然树链剖分通常跑不满.
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, int> li;
const int N = 2e5;
const ld Zero = 0, inf = 1/Zero;
struct Point {
ll x, y;
Point(ll x=0, ll y=0): x(x), y(y) {}
Point operator-(const Point& o) const
{
return Point(x-o.x, y-o.y);
}
friend ld slope(const Point& a, const Point& b)
{
return (ld)(a.y - b.y) / (a.x - b.x);
}
};
struct Convex_Hull {
Point S[N];
ld k[N];
int top;
Convex_Hull(): top(0) {}
void add(ll x, ll y)
{
Point p(x, y);
while (top > 1 && slope(p, S[top-1]) >= k[top-2]) --top;
k[top] = -inf;
if (top) k[top-1] = slope(p, S[top-1]);
S[top++] = p;
}
Point query(ld s)
{
return S[lower_bound(k, k+top, s, greater<ld>()) - k];
}
void clear()
{
top = 0;
}
} C;
vector<int> adj[N + 1];
vector<li> seq;
int fa[N + 1], sz[N + 1];
ll f[N + 1], s[N + 1], p[N + 1], q[N + 1], l[N + 1], d[N + 1];
bool g[N + 1];
int get_centroid(int u, const int& n)
{
int mx = 0, c = 0;
sz[u] = 1;
Rep (i, 0, adj[u].size()) {
int v = adj[u][i], ret;
if (g[v]) continue;
if ((ret = get_centroid(v, n))) c = ret;
mx = max(mx, sz[v]);
sz[u] += sz[v];
}
mx = max(mx, n-sz[u]);
return c ? c : (mx <= n/2 ? u : 0);
}
void dfs(int u)
{
Rep (i, 0, adj[u].size()) {
int v = adj[u][i];
if (!g[v]) {
seq.push_back(li(d[v] - l[v], v));
dfs(v);
}
}
}
void solve(int u, const int& n)
{
int x = get_centroid(u, n);
g[x] = true;
if (x != u) {
solve(u, n-sz[x]);
int y = x;
do {
y = fa[y];
if (d[x] - d[y] > l[x]) break;
f[x] = min(f[x], f[y] + (d[x]-d[y]) * p[x] + q[x]);
} while (y != u);
}
dfs(x);
sort(seq.begin(), seq.end(), greater<li>());
int z = x;
Rep (i, 0, seq.size()) {
int y = seq[i].second;
while (z && d[z] >= seq[i].first) {
C.add(d[z], f[z]);
z = z == u ? 0 : fa[z];
}
if (C.top) {
Point t = C.query(p[y]);
f[y] = min(f[y], t.y + p[y] * (d[y] - t.x) + q[y]);
}
}
C.clear();
seq.clear();
Rep (i, 0, adj[x].size()) {
int y = adj[x][i];
if (!g[y]) solve(y, sz[y]);
}
}
void cal_d(int u)
{
Rep (i, 0, adj[u].size()) {
int v = adj[u][i];
d[v] = d[u] + s[v];
cal_d(v);
}
}
int main()
{
int n, t;
scanf("%d%d", &n, &t);
For (i, 2, n) {
scanf("%d%lld%lld%lld%lld", &fa[i], &s[i], &p[i], &q[i], &l[i]);
adj[fa[i]].push_back(i);
}
cal_d(1);
fill_n(f+2, n-1, numeric_limits<ll>::max());
solve(1, n);
For (i, 2, n) printf("%lld\n", f[i]);
return 0;
}