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$。

$n \le 2 \times 10^5, p_v \le 10^6 , s_v, q_v, l_v \le 10^{12},$ 且任意城市到SZ市的总路程长度不超过 $10^{12}$。

Output

输出包含 $n-1$ 行,每行包含一个整数。

其中第 $v$ 行表示从城市 $v+1$ 出发,到达SZ市最少的购票费用。

同样请注意:输出不包含编号为 $1$ 的SZ市。

Solution

好题!

首先DP是很容易想到的,令$dp_u$表示点$u$的答案,$d_u$表示到根节点的距离,则:

考虑两个决策点$u, v, d_u < d_v$,若$u$优于$v$,则

这样我们只需要维护一个凸壳,然后将$p_i$在上面二分即可。

然而这是一个树形结构,凸壳不好维护,我们不妨用点分治来考虑转移。找到当前树的重心$P$,对于它以上的部分先递归下去求出其DP值,然后再考虑上面的点到下面的点的转移。我们将下面的点按它能到达的最小深度从大到小排序,然后将$P$到当前子树的根上的点依次加入凸壳,同时更新下面的点的答案即可。

时间复杂度 $T(n) = O(nlogn) + 2T(\frac{n}{2}) = O(nlog^2n)$

Source

#include <cstdio>
#include <algorithm>

#define For(i, j, k) for(int i = j; i <= k; i++)
#define Forr(i, j, k) for(int i = j; i >= k; i--)
#define getchar getchar_unlocked

using namespace std;

typedef long long LL;

const int N = 200010;

inline bool chkmin(int &x, int y){ if(x < y) return false; x = y; return true;}

inline LL Read(){
char c = getchar();
while(c < '0' || c > '9') c = getchar();
LL x = c - '0';
for(c = getchar(); c <= '9' && c >= '0'; c = getchar()) x = x * 10 + c - '0';
return x;
}

int Begin[N], Next[N], to[N], e;

void Add(int u, int v){
to[++e] = v;
Next[e] = Begin[u];
Begin[u] = e;
}

int n, Type;

int fa[N], sz[N];
LL dis[N], p[N], q[N], lim[N], dp[N];

bool cmpdep(int x, int y){
return dis[x] - lim[x] > dis[y] - lim[y];
}

bool vis[N];
int m, root, minsz;

void DFS(int o){
sz[o] = 1;
for(int i = Begin[o]; i; i = Next[i]){
int v = to[i];
if(vis[v]) continue;
DFS(v);
sz[o] += sz[v];
}
if(chkmin(minsz, max(sz[o], m - sz[o]))) root = o;
}

int A[N], B[N], l, r;

void DFS2(int o){
B[++r] = o;
for(int i = Begin[o]; i; i = Next[i]){
int v = to[i];
if(!vis[v]) DFS2(v);
}
}

void DFS3(int o){
for(int i = Begin[o]; i; i = Next[i]){
int v = to[i];
dis[v] += dis[o];
DFS3(v);
}
}

int st[N];
double s[N];

inline double Slope(int y, int x){
return 1.0 * (dp[y] - dp[x]) / (dis[y] - dis[x]);
}

void work(int o){
if(m <= 1) return;
root = o, minsz = m;
DFS(o);
int rt = fa[root];
for(int i = Begin[rt]; i; i = Next[i]) vis[to[i]] = true, m -= sz[to[i]];
work(o);
int u = rt;
l = r = 0;
A[++l] = u;
while(u != o) u = fa[u], A[++l] = u;
for(int i = Begin[rt]; i; i = Next[i]) DFS2(to[i]);
sort(B + 1, B + r + 1, cmpdep);

int j = 1, top = 0;
while(dis[B[j]] - lim[B[j]] > dis[A[1]] && j <= r) ++j;

For(i, 1, l){
while(top > 1 && s[top] < Slope(st[top], A[i])) --top;
st[++top] = A[i], s[top] = top > 1 ? Slope(st[top - 1], A[i]) : -1e18;

while((i == l || dis[B[j]] - lim[B[j]] > dis[A[i + 1]]) && j <= r){
int x = B[j], L = 1, R = top;
while(L < R){
int M = (L + R + 1) >> 1;
if(p[x] < s[M]) L = M;
else R = M - 1;
}
int y = st[L];
dp[x] = min(dp[x], p[x] * (dis[x] - dis[y]) + q[x] + dp[y]);
++j;
}
}

for(int i = Begin[rt]; i; i = Next[i]) m = sz[to[i]], work(to[i]);
}

int main(){
scanf("%d%d", &n, &Type);
For(i, 2, n){
fa[i] = Read(), dis[i] = Read(), p[i] = Read(), q[i] = Read(), lim[i] = Read();
Add(fa[i], i);
dp[i] = 1LL << 60;
}
dp[1] = 0;
DFS3(1);
m = n;
work(1);
For(i, 2, n) printf("%lld\n", dp[i]);
return 0;
}