Description

今年夏天，NOI在SZ市迎来了她30周岁的生日。来自全国 n 个城市的OIer们都会从各地出发，到SZ市参加这次盛会。

全国的城市构成了一棵以SZ市为根的有根树，每个城市与它的父亲用道路连接。为了方便起见，我们将全国的 n 个城市用 1 到 n 的整数编号。其中SZ市的编号为 1。对于除SZ市之外的任意一个城市 v，我们给出了它在这棵树上的父亲城市 fv 以及到父亲城市道路的长度 sv。

从城市 v 前往SZ市的方法为：选择城市 v 的一个祖先 a，支付购票的费用，乘坐交通工具到达 a。再选择城市 a 的一个祖先 b，支付费用并到达 b。以此类推，直至到达SZ市。

对于任意一个城市 v，我们会给出一个交通工具的距离限制 lv。对于城市 v 的祖先 a，只有当它们之间所有道路的总长度不超过 lv 时，从城市 v 才可以通过一次购票到达城市 a，否则不能通过一次购票到达。对于每个城市 v，我们还会给出两个非负整数 pv,qv 作为票价参数。若城市 v 到城市 a 所有道路的总长度为 d，那么从城市 v 到城市 a 购买的票价为 dpv+qv。

每个城市的OIer都希望自己到达SZ市时，用于购票的总资金最少。你的任务就是，告诉每个城市的OIer他们所花的最少资金是多少。

Input

第 1 行包含2个非负整数 n,t，分别表示城市的个数和数据类型（其意义将在后面提到）。输入文件的第 2 到 n 行，每行描述一个除SZ之外的城市。其中第 v 行包含 5 个非负整数 f_v,s_v,p_v,q_v,l_v，分别表示城市 v 的父亲城市，它到父亲城市道路的长度，票价的两个参数和距离限制。请注意：输入不包含编号为 1 的SZ市，第 2 行到第 n 行分别描述的是城市 2 到城市 n。

Output

输出包含 n-1 行，每行包含一个整数。其中第 v 行表示从城市 v+1 出发，到达SZ市最少的购票费用。同样请注意：输出不包含编号为 1 的SZ市。

Sample Input

7 3

1 2 20 0 3

1 5 10 100 5

2 4 10 10 10

2 9 1 100 10

3 5 20 100 10

4 4 20 0 10

Sample Output

40

150

0

149

300

150

HINT

对于所有测试数据，保证 0≤pv≤106，0≤qv≤1012，1≤fv<v；保证 0<sv≤lv≤2×1011，且任意城市到SZ市的总路程长度不超过 2×1011。

输入的 t 表示数据类型，0≤t<4，其中：

当 t=0 或 2 时，对输入的所有城市 v，都有 fv=v-1，即所有城市构成一个以SZ市为终点的链；

当 t=0 或 1 时，对输入的所有城市 v，都有 lv=2×1011，即没有移动的距离限制，每个城市都能到达它的所有祖先；

当 t=3 时，数据没有特殊性质。

n=2×10^5

---

思路

经典好题吧

知识点很全

首先考虑在一条链上怎么做？

斜率优化是一眼的

但是在树上怎么办？

我们要用一个节点的所有父亲来更新这个节点的dp值

考虑下分治算法来优化这个过程

在斜率优化的处理方式中有一种经典操作叫cdq分治

就是先处理一部分然后用这一部分更新剩下的部分，然后再递归处理剩下的部分

这里我们把问题模型抽象出来

如果把树划分成几个部分的话，我们考虑一个事情，就是说用来更新的祖先是一条链，可以更新到的儿子是一个子树

我们把祖先的链当成前一个部分，儿子当做另一个部分

也就是说我们先处理出前一个部分的所有信息，然后再用来更新儿子

考虑分治的过程

当前分治的树根是u，分治中心是rt

那么显然\([rt,u]\)这条链上的信息我们需要先处理出来

所以我们优先递归除了rt子树外的所有节点

然后再把\([rt,u]\)这一条链提出来更新rt的子树

注意因为有一个最大长度限制

所以我们进行更新的时候一定要注意把子树节点按照一定顺序排好，使得可以更新每一个节点的祖先数量单调不降

然后就对祖先维护凸壳就好了

---

注意一下点积不要爆longlong，用longdouble

还有找重心的时候如果当前节点siz是1需要特判一下不能作为重心

---

#include<bits/stdc++.h>

using namespace std;

typedef long double ld;

typedef long long ll;

ll read() {

  ll res = 0, w = 1; char c = getchar();

  while (!isdigit(c) && c != '-') c = getchar();

  if (c == '-') c = getchar(), w = -1;

  while (isdigit(c)) res = (res << 1) + (res << 3) + c - '0', c = getchar();

  return w * res;

}

const ll INF_of_ll = 1e18;

const ll N = 2e5 + 10; 

struct Node {

  ll id, val;

  Node() {}

  Node(ll id, ll val): id(id), val(val) {}

} rque[N];

bool operator < (const Node &a, const Node &b) {

  return a.val > b.val;

}

struct Vector {

  ll x, y;

  Vector() {}

  Vector(ll x, ll y): x(x), y(y) {}

} lque[N];

Vector operator - (const Vector &a, const Vector &b) {

  return Vector(a.x - b.x, a.y - b.y);

}

ld operator * (const Vector &a, const Vector &b) {

  return (ld) a.x * b.y - (ld) a.y * b.x;

}

struct Edge {

  ll v, w, nxt;

} E[N << 1];

ll topl, topr;

ll head[N], tot = 0;

ll n, prt[N], p[N], q[N], limit[N], dp[N];

ll siz[N], dis[N], F[N], vis[N], siz_all;

void addedge(ll u, ll v, ll w) {

  E[++tot] = (Edge) {v, w, head[u]};

  head[u] = tot;

}

void getsiz(ll u) {

  siz[u] = 1;

  for (ll i = head[u]; i; i = E[i].nxt) {

    ll v = E[i].v;

    if (vis[v]) continue;

    dis[v] = dis[u] + E[i].w;

    getsiz(v);

    siz[u] += siz[v];

  }

}

void getrt(ll u, ll &rt) {

  F[u] = siz_all - siz[u];

  for (ll i = head[u]; i; i = E[i].nxt) {

    ll v = E[i].v;

    if (vis[v]) continue;

    getrt(v, rt);

    F[u] = max(F[u], siz[v]);

  }

  if (F[u] < F[rt] && siz[u] > 1) rt = u;

} 

void dfs(ll u) {

  rque[++topr] = (Node) {u, dis[u] - limit[u]};

  for (ll i = head[u]; i; i = E[i].nxt)

    if (!vis[E[i].v]) dfs(E[i].v);

}

ll calc(ll v, Vector u) {

  return u.y + (dis[v] - u.x) * p[v] + q[v];

}

void solve(ll u, ll cursiz) {

  if (cursiz == 1) return;

  ll rt = 0;

  getsiz(u);

  F[rt] = siz_all = cursiz;

  getrt(u, rt);

  for (ll i = head[rt]; i; i = E[i].nxt)

    vis[E[i].v] = 1;

  solve(u, cursiz - siz[rt] + 1);

  topl = topr = 0;

  for (ll i = head[rt]; i; i = E[i].nxt)

    dfs(E[i].v);

  sort(rque + 1, rque + topr + 1);

  ll cur = rt;

  lque[0] = Vector(dis[rt] + 1, INF_of_ll);

  for (ll i = 1; i <= topr; i++) {

    while (cur != prt[u] && dis[cur] >= rque[i].val) {

      Vector now(dis[cur], dp[cur]);

      while (topl > 1 && (lque[topl] - lque[topl - 1]) * (now - lque[topl - 1]) > 0.0) topl--;

      lque[++topl] = now;

      cur = prt[cur];

    }

    if (topl) {

      ll l = 1, r = topl, res = 1, now = rque[i].id;

      while (l <= r) {

        ll mid = (l + r) >> 1;

        if (calc(now, lque[mid]) <= calc(now, lque[mid - 1])) res = mid, l = mid + 1;

        else r = mid - 1;

      }

      dp[now] = min(dp[now], calc(now, lque[res]));

    }

  }

  for (ll i = head[rt]; i; i = E[i].nxt)

    solve(E[i].v, siz[E[i].v]);

}

int main() {

#ifdef dream_maker

  freopen("input.txt", "r", stdin);

#endif

  n = read();

  ll typ = read();

  for (ll i = 2; i <= n; i++) {

    prt[i] = read();

    ll w = read();

    addedge(prt[i], i, w);

    p[i] = read();

    q[i] = read();

    limit[i] = read();

    dp[i] = INF_of_ll;

  }

  solve(1, n);

  for (ll i = 2; i <= n; i++)

    printf("%lld\n", dp[i]);

  return 0;

}