感觉是noi2014中最有价值的一道题了
我们先考虑链上这个问题怎么做……
如果没限制，那就是SB的斜率优化
我们可以得到这个式子(f[j]-f[k])/(s[j]-s[k])<p[i]
点横坐标是单调的，我们只要维护凸壳然后二分即可
有距离限制？好像不好弄，不过我们记得cash那道坐标不单调的题我们是可以用cdq分治的
这道题也一样，划分，考虑左半部分对右半部分的影响
我们只要对右半部分距离限制排序然后依次加点维护凸壳然后二分即可
换到树上来那就是点分治啦，
我们找重心，先做重心子树外（就是包含根的那部分），做完之后
考虑重心的祖先对子树的影响，我们完全可以如法炮制
然后不断向下递归处理即可
这样noi2014的传统题就做完啦！
const inf=;
eps=1e-10; type node=record
po,next:longint;
end;
point=record
x,y:int64;
end; var h,fp,p,fa,mx,s,q,b:array[..] of longint;
a:array[..] of point;
cut:array[..] of boolean;
e:array[..] of node;
w,f,d,kp,bp,lim:array[..] of int64;
x,t,i,len,n,ty,r:longint; function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end; procedure min(var a:int64; b:int64);
begin
if a>b then a:=b;
end; procedure add(x,y:longint);
begin
inc(len);
e[len].po:=y;
e[len].next:=p[x];
p[x]:=len;
end; procedure bfs(st:longint);
var i,f,x,y:longint;
begin
f:=;
r:=;
q[]:=st;
while f<=r do
begin
x:=q[f];
i:=p[x];
while i<> do
begin
if not cut[i] then
begin
inc(r);
q[r]:=e[i].po;
end;
i:=e[i].next;
end;
inc(f);
end;
end; procedure swap(var a,b:longint);
var c:longint;
begin
c:=a;
a:=b;
b:=c;
end; function cmp(i,j:longint):boolean;
begin
exit(lim[i]-d[i]<lim[j]-d[j]);
end; procedure sort(l,r:longint);
var i,j,x:longint;
begin
i:=l;
j:=r;
x:=b[(l+r) shr ];
repeat
while cmp(b[i],x) do inc(i);
while cmp(x,b[j]) do dec(j);
if i<=j then
begin
swap(b[i],b[j]);
inc(i);
dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end; function getk(i,j:longint):extended;
begin
exit((a[i].y-a[j].y)/(a[i].x-a[j].x));
end; function find(l,r,x:longint):longint;
var m:longint;
s1,s2:int64;
begin
while l<r do
begin
m:=(l+r) shr ;
s1:=a[h[m]].y+a[h[m]].x*kp[x];
s2:=a[h[m+]].y+a[h[m+]].x*kp[x];
if s1>s2 then l:=m+
else r:=m;
end;
exit(h[l]);
end; procedure cdq(root:longint);
var i,j,x,mid,m,y:longint;
begin
bfs(root);
if r= then exit;
mid:=;
for i:=r downto do
begin
x:=q[i];
s[x]:=;
mx[x]:=;
j:=p[x];
while j<> do
begin
y:=e[j].po;
if not cut[j] then
begin
s[x]:=s[x]+s[y];
mx[x]:=max(mx[x],s[y]);
end;
j:=e[j].next;
end;
mx[x]:=max(mx[x],r-s[x]);
if mx[x]<mx[mid] then mid:=x;
end;
if root<>mid then
begin
cut[fp[mid]]:=true;
cdq(root);
m:=;
x:=fa[mid];
while x<>root do
begin
inc(m);
a[m].x:=-d[x]; //为了方便改变一下形式
a[m].y:=f[x];
x:=fa[x];
end;
inc(m);
a[m].x:=-d[x];
a[m].y:=f[x]; bfs(mid);
for i:= to r do
b[i]:=q[i];
sort(,r);
t:=;
j:=;
for i:= to r do
begin
x:=b[i];
while (j<=m) and (a[j].x<=lim[x]-d[x]) do
begin
while (t>) and (getk(j,h[t])-eps<getk(h[t],h[t-])) do dec(t);
inc(t);
h[t]:=j;
inc(j);
end;
if t> then
begin
y:=find(,t,x);
min(f[x],a[y].y+kp[x]*(d[x]+a[y].x)+bp[x]);
end;
end;
end;
for i:= to r do
begin
x:=q[i];
if d[x]-d[mid]<=lim[x] then
min(f[x],f[mid]+kp[x]*(d[x]-d[mid])+bp[x]);
end;
i:=p[mid];
while i<> do
begin
if not cut[i] then cdq(e[i].po);
i:=e[i].next;
end;
end; begin
readln(n,ty);
for i:= to n do
begin
readln(fa[i],w[i],kp[i],bp[i],lim[i]);
add(fa[i],i);
fp[i]:=len;
f[i]:=inf;
end;
bfs();
for i:= to r do
begin
x:=q[i];
d[x]:=d[fa[x]]+w[x];
end;
mx[]:=n+;
f[]:=;
cdq();
for i:= to n do
writeln(f[i]);
end.