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\) 购买的票价为 \(d\times p_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:


Sample Output:


题解:


这题有点工业~

首先 \(O(n^2)\) 的算法很简单,按照DFS序进行如下DP就可以了(其中 \(v\)\(u\) 的祖先,且 \(dis_{v, u} \le l_u\)

发现这个递推式可以斜率优化,即若 \(i\lt k\lt j\)\(k\) 优于 \(j\) ,则:

\[ \frac{f_k-f_i}{d_k-d_i} \lt p_j\]

但是 \(p_j\) 并不是单调的,所以我们需要在一个凸壳上二分。

并且这是在一颗树上,我们可以利用点分治。

具体来说,每一次分治:

  1. 找到重心;
  2. 递归解决含有根节点的一部分;
  3. 对于其他子树的节点,排序以后从含有根节点的部分中的节点更新;
  4. 递归处理每一棵子树。

思路还是很清晰的。