BZOJ3672 Ticket

{$INLINE ON}
program bzoj3672;

type point=record x,y:int64; end;
     tedge=record n,next:longint; end;
     pnode=^tnode;
     tnode=record
        v,e:point;
        p:longint;
        l,r:pnode;
     end;

const maxn=200017;
      maxm=200017;
      maxint=longint($3f3f3f3f);
      eps=1e-9;
      nuv:point=(x:-1;y:-1);
      nev:point=(x:0;y:0);

var g,fa,anc,q,size,sons:array[0..maxn] of longint;
    a,b,f,dr,lim:array[0..maxn] of int64;
    mem:array[0..maxm] of tedge;
    flag:array[0..maxn] of boolean;
    n,memsize,casetype,frt,rer:longint;
    treap,null:pnode;

operator <(a,b:point) c:boolean; inline; begin exit((a.x<b.x)or((a.x=b.x)and(a.y<b.y))); end;
operator -(a,b:point) c:point; inline; begin c.x:=a.x-b.x; c.y:=a.y-b.y; end;
operator *(a,b:point) c:extended; inline; begin exit(extended(a.x)*b.y-extended(b.x)*a.y); end;
operator =(a,b:point) c:boolean; inline; begin exit((a.x=b.x)and(a.y=b.y)); end;

function min(i,j:int64):int64; inline; begin if i<j then exit(i) else exit(j); end;
function max(i,j:int64):int64; inline; begin if i>j then exit(i) else exit(j); end;

function sgn(r:extended):longint; inline;                begin
if r<-eps then exit(-1); if r>eps then exit(1); exit(0); end;

procedure insnbs(u,v:longint); inline;                                          begin
inc(memsize); mem[memsize].n:=v; mem[memsize].next:=g[u];  g[u]:=memsize;       end;

procedure treap_init;                                                                           begin
new(null); with null^ do begin v.x:=-1; v.y:=-1; p:=maxint; l:=null; r:=null; end; treap:=null; end;

procedure lrot(var i:pnode); inline; var j:pnode;
begin j:=i^.r; i^.r:=j^.l; j^.l:=i; i:=j; end;

procedure rrot(var i:pnode); inline; var j:pnode;
begin j:=i^.l; i^.l:=j^.r; j^.r:=i; i:=j; end;

procedure insert(var i:pnode;j:point);
begin
if i=null then begin
        new(i); with i^ do begin
                v:=j; p:=random(maxint); e:=nev; l:=null; r:=null;
        end;
end else if j<i^.v then begin
        insert(i^.l,j); if i^.l^.p<i^.p then rrot(i);
end else begin
        insert(i^.r,j); if i^.r^.p<i^.p then lrot(i);
end;
end;

procedure delete(var i:pnode;j:point);
begin
if j=i^.v then
        if i^.l=null then i:=i^.r
        else if i^.r=null then i:=i^.l
        else if i^.l^.p<i^.r^.p then begin
                rrot(i); delete(i^.r,j);
        end else begin
                lrot(i); delete(i^.l,j);
        end
else if j<i^.v then delete(i^.l,j) else delete(i^.r,j);
end;

function prev(i:pnode;j:point):pnode; inline;
begin
prev:=null; while i<>null do
        if not(i^.v<j) then i:=i^.l
        else begin prev:=i; i:=i^.r; end;
end;

function next(i:pnode;j:point):pnode; inline;
begin
next:=null; while i<>null do
        if (i^.v<j)or(i^.v=j) then i:=i^.r
        else begin next:=i; i:=i^.l; end;
end;

procedure update(i:point);
var t1,t2:pnode;
begin
t1:=treap; t2:=next(treap,i); while t1^.v<>i do
        if i<t1^.v then t1:=t1^.l else t1:=t1^.r;
if (t2=null)or(t1=null) then t1^.e:=nev else t1^.e:=t2^.v-t1^.v;
end;

procedure addpoint(a:point);
var rp,lp,np:point;
begin
lp:=prev(treap,a)^.v; if lp=nuv then begin
        rp:=next(treap,a)^.v; while true do begin
                np:=next(treap,rp)^.v; if np=nuv then break;
                if sgn((rp-a)*(np-a))>=0 then begin
                        delete(treap,rp); rp:=np;
                end else break;
        end; insert(treap,a); update(a); exit;
end;
rp:=next(treap,a)^.v; if rp=nuv then begin
        lp:=prev(treap,a)^.v; while true do begin
                np:=prev(treap,lp)^.v; if np=nuv then break;
                if sgn((lp-a)*(np-a))<=0 then begin
                        delete(treap,lp); lp:=np;
                end else break;
        end; insert(treap,a); if lp<>nuv then update(lp); exit;
end;
if sgn((a-lp)*(rp-lp))>=0 then exit;
while true do begin
        np:=prev(treap,lp)^.v; if np=nuv then break;
        if sgn((a-lp)*(np-lp))>=0 then begin
                delete(treap,lp); lp:=np;
        end else break;
end;
while true do begin
        np:=next(treap,rp)^.v; if np=nuv then break;
        if sgn((a-rp)*(np-rp))<=0 then begin
                delete(treap,rp); rp:=np;
        end else break;
end; insert(treap,a);
update(a); update(prev(treap,a)^.v);
end;

function tanpoint(a:point):point;
var t1:pnode;
begin
tanpoint.x:=0; tanpoint.y:=0;
if treap=null then begin tanpoint.x:=maxint; exit; end;
t1:=treap; while t1<>null do begin
        if sgn(t1^.e*a)<0 then t1:=t1^.r
        else begin tanpoint:=t1^.v; t1:=t1^.l; end;
end;
end;

function centre(root:longint):longint;
var i,j,head,tail,t1,ans:longint;
begin
frt:=0; rer:=1; q[1]:=root; while frt<rer do begin
        inc(frt); head:=q[frt]; t1:=g[head];
        while t1<>0 do begin tail:=mem[t1].n;
                if not flag[tail] then begin
                        inc(rer); q[rer]:=tail;
                end; t1:=mem[t1].next;
        end; size[head]:=0; sons[head]:=0;
end; ans:=maxint; for i:=rer downto 1 do begin
        j:=q[i]; inc(size[j]); sons[fa[j]]:=max(sons[fa[j]],size[j]);
        t1:=max(sons[j],rer-size[j]); if t1<ans then begin
                ans:=t1; centre:=j;
        end; inc(size[fa[j]],size[j]);
end;
end;

procedure qsort(l,r:longint);
var i,j,k,o:longint;
begin
i:=l; j:=r; k:=q[l+random(r-l+1)];
repeat
        while lim[q[i]]>lim[k] do inc(i);
        while lim[q[j]]<lim[k] do dec(j);
        if i<=j then begin
                o:=q[i]; q[i]:=q[j]; q[j]:=o;
                inc(i); dec(j);
        end;
until i>j;
if i<r then qsort(i,r);
if j>l then qsort(l,j);
end;

procedure update(u,root:longint);
var i,j,ac,head,tail,t1:longint;
    tp:point;
begin
frt:=0; rer:=1; q[1]:=u; while frt<rer do begin
        inc(frt); head:=q[frt]; t1:=g[head];
        while t1<>0 do begin tail:=mem[t1].n;
                if not flag[tail] then begin
                        inc(rer); q[rer]:=tail;
                end; t1:=mem[t1].next;
        end;
end; qsort(1,rer); treap:=null;
ac:=0; head:=u; while head<>root do begin
        head:=fa[head]; inc(ac); anc[ac]:=head;
end; if ac>0 then begin
        j:=1; for i:=1 to rer do begin u:=q[i];
                while (j<=ac)and(dr[anc[j]]>=lim[u]) do begin
                        tp.x:=f[anc[j]]; tp.y:=dr[anc[j]]; addpoint(tp); inc(j);
                end; if j>1 then begin
                        tp.x:=a[u]; tp.y:=1; tp:=tanpoint(tp);
                        f[u]:=min(f[u],dr[u]*a[u]+b[u]+tp.x-a[u]*tp.y);
                end;
        end;
end else begin
        for i:=1 to rer do begin u:=q[i];
                if dr[root]>=lim[u] then
                        f[u]:=min(f[u],dr[u]*a[u]+b[u]+f[root]-a[u]*dr[root]);
        end;
end;
end;

procedure init;
var i,head,t1:longint;
begin
fillchar(g,sizeof(g),0); memsize:=1;
readln(n,casetype); for i:=2 to n do begin
        readln(fa[i],dr[i],a[i],b[i],lim[i]); insnbs(fa[i],i);
end; frt:=0; rer:=1; q[1]:=1; while frt<rer do begin
        inc(frt); head:=q[frt]; inc(dr[head],dr[fa[head]]);
        t1:=g[head]; while t1<>0 do begin
                inc(rer); q[rer]:=mem[t1].n; t1:=mem[t1].next;
        end; lim[head]:=dr[head]-lim[head];
end; fillchar(flag,sizeof(flag),0); fillchar(f,sizeof(f),$3f); f[1]:=0;
end;

procedure work(root:longint);
var u,t1:longint;
begin
u:=centre(root); flag[u]:=true;
if u<>root then begin
        work(root); update(u,root); work(u);
end else begin
        update(u,root); t1:=g[u]; while t1<>0 do begin
                if not flag[mem[t1].n] then work(mem[t1].n);
                t1:=mem[t1].next;
        end;
end;
end;

procedure answer; var i:longint;
begin for i:=2 to n do writeln(f[i]); end;

begin
treap_init;
init;
work(1);
answer;
end.