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市。
Analysis：
不难想到DP方程如下：
$f[i] = min(f[j], (D_i-D_j)*p_i+q_i)$
其中，$D_i$为根到$i$的距离，且$j \in anc(i)$，$(D_i-D_j) <= l_i$
运用斜率优化的套路，设有决策$j$,$k$，且$dep_j > dep_k$，$k$优于$j$当且仅当：
可化为 $\frac{f[k]-f[j]}{D_k-D_j} > p_i$，这是斜率DP的基本形式，注意到$D_i$是单调的，而$p_i$不是，说明在具体实现时，我们不能从队尾弹出元素，并且对于一个$p_i$，需要用二分找到它的最优解
接下来，我们发现DP的东西是一棵树，不同于线性DP，需要用树的点分治来处理：
１．首先找到树的重心$H$，把树从这里砍开（注意要避免被菊花图卡掉，需要把$H$和根放在一起，然后砍开$H$的所有子节点）
２．把$H$和根的一块继续递归处理。
３．把$H$下面的众子节点们按所能到达的最小祖先深度排序，深度越大排在越后面
４．按顺序处理众子节点们，从$H$开始，每次把还未加入的自己可达的祖先们（决策们）加进去，并更新$f$（用斜率DP＋二分处理）
５．递归处理$H$的子节点们的子树
（ps: 我们维护的本来是一个正常的下凸壳，但是由于D值是由大往小加的[意思就是横坐标是从右往左加入的]，所以维护的是一个上凸壳）
Thoughts：
我神奇地认为自己非常好的理解了这题（勿喷。。）
终于好像搞明白了斜率DP？？？（某斜率 > 某值，则斜率递增为下凸壳，某斜率f < 某值，反之 ->-> 实际上就是要维护后面的都不比之前的优吧，一个不比一个优，如果加一个新的不满足凸性，那么说明新的比某老的优。。就要把老的弹掉，因为老的没有用了啊哈哈。。至于队尾弹。是因为某值变了啊，并且如果你要弹掉队尾的话，某值还要单调，否则你可能把后面你要用的符合条件的东西弹掉了，像这题某值不单调，就二分找第一个满足条件的，找到以后因为斜率是。。。的，所以一个不比一个优，所以就是找的的第一个满足条件的就是最优的决策）<-<-我废话好多。。
不过这样子在树的结构上运用树的点分治作DP，是个非常好的思路！
还有找重心就是dfs一遍然后找出子节点个数，和用总数减去子节点个数就可以统计，也非常好
Code：
//2017.5.25 Miaomiao
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
#define For(i, a, b) for(int i = (a); i <= (int)(b); ++i)
#define N (200000+5)
LL p[N], q[N], lim[N], dp[N], dis[N], siz[N];
int fa[N], A[N], B[N], tu[N];
int en, Begin[N], Nxt[N], To[N];
bool vis[N];
inline bool Chkmin(int &a, int b){if(a<b) return true; a=b; return false;}
inline void Add(int a, int b){
To[++en] = b; Nxt[en] = Begin[a]; Begin[a] = en;
}
inline bool Bcmp(int a, int b){
return dis[a]-lim[a] > dis[b]-lim[b];
}
inline double Slope(int b, int a){
return 1.0*(dp[b]-dp[a])/(dis[b]-dis[a]);
}
void To_Root_Dis(int now){
for(int i = Begin[now]; i; i = Nxt[i]){
dis[To[i]] += dis[now];
To_Root_Dis(To[i]);
}
}
int m, an, bn, hvy, Mins;
double st[N];
void FindHeavy(int now){
siz[now] = 1;
for(int i = Begin[now]; i; i = Nxt[i]){
if(vis[To[i]]) continue;
FindHeavy(To[i]); siz[now] += siz[To[i]];
}
if(!Chkmin(Mins, max(siz[now], m-siz[now]))) hvy = now;
}
void Dfs(int now){
B[++bn] = now;
for(int i = Begin[now]; i; i = Nxt[i]){
if(vis[To[i]]) continue;
Dfs(To[i]);
}
}
void Solve(int H){
if(m <= 1) return;
hvy = H; Mins = m;
FindHeavy(H);
int rt = fa[hvy];
for(int i = Begin[rt]; i; i = Nxt[i]) vis[To[i]] = true, m -= siz[To[i]];
Solve(H);
int tnow = rt;
an = bn = 0;
while(tnow != H) A[++an] = tnow, tnow = fa[tnow];
A[++an] = H;
for(int i = Begin[rt]; i; i = Nxt[i]) Dfs(To[i]);
sort(B+1, B+bn+1, Bcmp);
int bp = 1, now, tp;
while(bp <= bn && dis[B[bp]]-lim[B[bp]] > dis[rt]) ++bp;
tp = 0;
int L, R, mid, v, tx;
For(i, 1, an){
now = A[i];
while(tp>1 && Slope(now, tu[tp]) > st[tp]) --tp;
tu[++tp] = now; st[tp] = tp==1? -1.0*(1LL<<60): Slope(now, tu[tp-1]);
while(bp <= bn && (i==an || dis[B[bp]]-lim[B[bp]] > dis[A[i+1]])){
L = 1; R = tp; v = B[bp];
while(L < R){
mid = (L+R+1)>>1;
if(p[v] < st[mid]) L = mid;
else R = mid-1;
}
tx = tu[L];
dp[v] = min(dp[v], dp[tx]+p[v]*(dis[v]-dis[tx])+q[v]);
++bp;
}
}
for(int i = Begin[rt]; i; i = Nxt[i]) m = siz[To[i]], Solve(To[i]);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
int n, t;
scanf("%d%d", &n, &t);
For(i, 2, n){
scanf("%d%lld%lld%lld%lld", &fa[i], &dis[i], &p[i], &q[i], &lim[i]);
Add(fa[i], i);
dp[i] = 1LL<<60;
}
To_Root_Dis(1);
m = n; Solve(1);
For(i, 2, n) printf("%lld\n", dp[i]);
return 0;
}