Description
今年夏天，NOI在SZ市迎来了她30周岁的生日。来自全国 n 个城市的OIer们都会从各地出发，到SZ市参加这次盛会。
全国的城市构成了一棵以SZ市为根的有根树，每个城市与它的父亲用道路连接。为了方便起见，我们将全国的 n 个城市用 1 到 n 的整数编号。其中SZ市的编号为 1。对于除SZ市之外的任意一个城市 v，我们给出了它在这棵树上的父亲城市 fv 以及到父亲城市道路的长度 sv。
从城市 v 前往SZ市的方法为：选择城市 v 的一个祖先 a，支付购票的费用，乘坐交通工具到达 a。再选择城市 a 的一个祖先 b，支付费用并到达 b。以此类推，直至到达SZ市。
对于任意一个城市 v，我们会给出一个交通工具的距离限制 lv。对于城市 v 的祖先 a，只有当它们之间所有道路的总长度不超过 lv 时，从城市 v 才可以通过一次购票到达城市 a，否则不能通过一次购票到达。对于每个城市 v，我们还会给出两个非负整数 pv,qv 作为票价参数。若城市 v 到城市 a 所有道路的总长度为 d，那么从城市 v 到城市 a 购买的票价为 dpv+qv。
每个城市的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市。
f[w]=min(f[u]+(dep[w]-dep[u])*p[w])+q[w]
=min(f[u]-dep[u]*p[w])+(q[w]+p[w]*dep[w])
(dep[w]-l[w]<=dep[u]<dep[w])
将(f[u],dep[u])看作平面上的点，最优决策可以在凸包上二分出来
在树上dfs的过程中，用线段树套栈维护当前点到根的路径的凸包，支持在凸包末端插入点、撤销插入，查询某个后缀的最优决策，为保证复杂度末端插入时要用二分确定弹出多少元素
时间复杂度O(nlog2n)
#include<cstdio> typedef long long i64; const int N=200007; char buf[N*100],*ptr=buf-1; template<class T> void _(T&x){ x=0; int c=*++ptr; while(c<48)c=*++ptr; while(c>47)x=x*10+c-48,c=*++ptr; } int n,t; int fa[N],es[N],enx[N],e0[N],ev[N],ep=2; i64 dep[N],s[N],l[N],p[N],q[N],f[N],md; void mins(i64&a,i64 b){if(a>b)a=b;} bool chk(int w,int b,int a){ return double(f[w]-f[b])*(dep[b]-dep[a])-double(f[b]-f[a])*(dep[w]-dep[b])<=0; } int *os1[N*40],os2[N*40],op=0; void set(int&x,int y){ os1[op]=&x; os2[op++]=x; x=y; } struct stk{ int*ss,sp; void cal(int w){ int L=0,R=sp,M; while(L<R){ M=(L+R)>>1; int a=ss[M],b=ss[M+1]; if(f[a]-f[b]<(dep[a]-dep[b])*p[w])R=M; else L=M+1; } int x=ss[L]; mins(f[w],f[x]+(dep[w]-dep[x])*p[w]+q[w]); } void ins(int w){ int L=0,R=sp,M; while(L<R){ M=(L+R)>>1; int a=ss[M],b=ss[M+1]; if(chk(w,b,a))R=M; else L=M+1; } set(sp,R+1); set(ss[sp],w); } }tr[524288]; int mem[524288*10],*mp=mem; int mx; void cal(int w,int x){ if(x>=mx*2)return; if(x&1){ if(tr[x].sp<0||tr[x].ss[tr[x].sp][dep]<md)return; if(tr[x].ss[0][dep]>=md){ tr[x].cal(w); return; } } cal(w,x<<1^1); cal(w,x<<1); } void dfs(int w,int D){ dep[w]=dep[fa[w]]+s[w]; if(w!=1){ md=dep[w]-l[w]; f[w]=1ll<<62; cal(w,1); } int op0=op; for(int i=mx+D;i;i>>=1)if(i&1)tr[i].ins(w); for(int i=e0[w];i;i=enx[i])dfs(es[i],D+1); while(op>op0)--op,*os1[op]=os2[op]; } void build(int w,int l,int r){ if(l+1<r){ int m=(l+r)>>1; build(w<<1,l,m); build(w<<1^1,m,r); } if(w&1)tr[w].ss=mp,mp+=r-l; tr[w].sp=-1; } int mxd=1; void gd(int w,int D){ if(D>mxd)mxd=D; for(int i=e0[w];i;i=enx[i])gd(es[i],D+1); } int main(){ fread(buf,1,sizeof(buf),stdin)[buf]=0; _(n);_(t); for(int i=2;i<=n;++i){ _(fa[i]);_(s[i]); es[ep]=i;enx[ep]=e0[fa[i]];e0[fa[i]]=ep++; _(p[i]);_(q[i]);_(l[i]); } gd(1,1); for(mx=1;mx<mxd;mx<<=1); build(1,0,mx); dfs(1,0); for(int i=2;i<=n;++i)printf("%lld ",f[i]); return 0; }