HYSBZ 3672 購票

Description

 今年夏天，NOI在SZ市迎來了她30周歲的生日。來自全國 n 個城市的OIer們都會從各地出發，到SZ市參加這次盛會。

       全國的城市構成了一棵以SZ市為根的有根樹，每個城市與它的父親用道路連接配接。為了友善起見，我們将全國的n個城市用 1 到 n 的整數編号。其中SZ市的編号為 1。對于除SZ市之外的任意一個城市 v，我們給出了它在這棵樹上的父親城市 f

v  以及到父親城市道路的長度 s

v。

從城市 v 前往SZ市的方法為：選擇城市 v 的一個祖先 a，支付購票的費用，乘坐交通工具到達 a。再選擇城市 a 的一個祖先 b，支付費用并到達 b。以此類推，直至到達SZ市。

對于任意一個城市 v，我們會給出一個交通工具的距離限制 l

v。對于城市 v 的祖先 a，隻有當它們之間所有道路的總長度不超過 l

v 時，從城市 v 才可以通過一次購票到達城市 a，否則不能通過一次購票到達。對于每個城市 v，我們還會給出兩個非負整數 p

v,q

v  作為票價參數。若城市 v 到城市 a 所有道路的總長度為 d，那麼從城市 v 到城市 a 購買的票價為 dp

v+q

v。

每個城市的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
70
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

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<bitset>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define rep(i,j,k) for (int i = j;i <= k; i++)
#define repd(i,j,k) for (int i = j;i >= k; i--)
#define loop(i,j,k) for (int i = j;i != -1; i = k[i])
typedef long long  LL;
const int low(int x) { return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int maxn = 4e5 + 10;
const LL Max = 1LL << 62;
int n, m, fa[maxn];
LL p[maxn], q[maxn], d[maxn], f[maxn], x, L[maxn];

bool cmp(const int &x, const int &y)
{
  return d[x] - L[x] > d[y] - L[y];
}

struct Tree
{
  int ft[maxn], nt[maxn], u[maxn], sz;
  int mx[maxn], ct[maxn], vis[maxn];
  int a[maxn], b[maxn], c[maxn];
  void clear(int n)
  {
    mx[sz = 0] = INF;
    rep(i, vis[0] = 1, n) vis[i] = 0, ft[i] = -1;
  }
  void AddEdge(int x, int y)
  {
    u[sz] = y;  nt[sz] = ft[x]; ft[x] = sz++;
    u[sz] = x;  nt[sz] = ft[y]; ft[y] = sz++;
  }
  int dfs(int x, int fa, int sum)
  {
    int y = mx[x] = (ct[x] = 1) ^ 1;
    loop(i, ft[x], nt)
    {
      if (vis[u[i]] || u[i] == fa) continue;
      int z = dfs(u[i], x, sum);
      ct[x] += ct[u[i]];
      mx[x] = max(mx[x], ct[u[i]]);
      y = mx[y] < mx[z] ? y : z;
    }
    mx[x] = max(mx[x], sum - ct[x]);
    return mx[x] < mx[y] ? x : y;
  }
  bool check(int x, int y, int z)
  {
    return 1.0*(f[y] - f[x]) / (d[y] - d[x]) <= 1.0*(f[z] - f[y]) / (d[z] - d[y]);
  }
  void get(int x, int fa, int &t)
  {
    c[++t] = x;
    loop(i, ft[x], nt)
    {
      if (u[i] == fa || vis[u[i]]) continue;
      get(u[i], x, t);
    }
  }
  int find(int l, int r, LL x)
  {
    if (l == r) return b[r];
    int q = l, h = r - 1, m;
    while (q <= h)
    {
      m = q + h >> 1;
      if (1.0*(f[b[m + 1]] - f[b[m]]) / (d[b[m + 1]] - d[b[m]]) <= x) h = m - 1;
      else q = m + 1;
    }
    return b[q];
  }
  void work(int x, int sum)
  {
    //if (sum < 2) return;
    int y = dfs(x, -1, sum);
    vis[y] = 1;
    if (x != y) work(x, sum - ct[y]);
    int t = -1, l = 0, r = -1, tt, g = 0;
    loop(i, fa[y], fa)
    { 
      if (i == 0) break;
      a[++t] = i;
      if (vis[i]) break;
    }
    get(y, fa[y], tt = -1);
    sort(c, c + tt + 1, cmp);
    rep(i, 0, tt)
    {
      while (g <= t&&d[a[g]] >= d[c[i]] - L[c[i]])
      {
        while (l < r&&check(b[r - 1], b[r], a[g])) --r;
        b[++r] = a[g++];
      }
      if (l > r) continue;
      int k = find(l, r, p[c[i]]);
      //while (k > l && 1.0*(f[b[k]] - f[b[k - 1]]) / (d[b[k]] - d[b[k - 1]]) <= p[c[i]]) k--;
      //k = b[k];
      f[c[i]] = min(f[c[i]], f[k] + (d[c[i]] - d[k])*p[c[i]] + q[c[i]]);
    }
    loop(i, ft[y], nt)
    {
      if (vis[u[i]] || u[i] == fa[y]) continue;
      work(u[i], ct[u[i]]);
    }
    vis[y] = 0;
  }
}solve;

int main()
{
  scanf("%d%d", &n, &m);
  solve.clear(n);
  d[1] = f[1] = fa[1] = 0;
  rep(i, 2, n)
  {
    scanf("%d%lld%lld%lld%lld", &fa[i], &x, &p[i], &q[i], &L[i]);
    solve.AddEdge(i, fa[i]);
    d[i] = d[fa[i]] + x;
    f[i] = Max - 1 << 1;
  }
  solve.work(1, n);
  rep(i, 2, n) printf("%lld\n", f[i]);
  return 0;
}