题解：

这位仁兄您点进来的题解是cdq+点分+斜率优化的。

吐草：细节是真多……

先推一波式子：

$dp[i]=min(dp[j]+(dis[i]-dis[j])*p[i]+q[i])=dis[i]*p[i]+q[i]+min(dp[j]-dis[j]*p[i])$

$min()$里面那个明显是斜率优化。

这个转移要求更新i时1~i路径上的所有点均已经是最优解。

然后你就想到了$cdq$分治。

$cdq$分治一段区间操作：分治左区间，处理左区间->右区间，分治右区间;

毒瘤题购票树上操作：处理深度浅的，处理浅的->深的，处理深度深的。

这好像是一样的。

所以我们可以把$cdq$中的$mid$换成点分中的重心。

然后重心上面的更新重心和重心下面的，再让重心更新重心下面的。

然后就过了。

～～～

有几个大坑：

1.叉积爆$long long$，要用$double$除法。

2.由于让$b$值最小我们应该维护下凸包，但是$dis$是倒序加入。不妨将$x,y$都取反，然后维护正向加入的上凸包。

代码：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define N 200050#define ll long long #define db long double#define nd (ve.size()-1)const int inf = 0x3f3f3f3f;const db eps = 1e-8;inline ll rd(){    ll f=1,c=0;char ch=getchar();    while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}    return f*c;}int n,t,hed[N],cnt;struct pnt{    int fa;    ll p,q,l;}c[N];struct EG{    int to,nxt;    ll v;}e[2*N];void ae(int f,int t,ll v){    e[++cnt].to = t;    e[cnt].nxt = hed[f];    e[cnt].v = v;    hed[f] = cnt;}ll dis[N];void dfs(int u,int fa){    for(int j=hed[u];j;j=e[j].nxt)    {        int to = e[j].to;        if(to==fa)continue;        dis[to] = dis[u] + e[j].v;        dfs(to,u);    }}int rt,sum,mrk[N],w[N],siz[N];void get_rt(int u,int fa){    w[u] = 0,siz[u] = 1;    for(int j=hed[u];j;j=e[j].nxt)    {        int to = e[j].to;        if(to==fa||mrk[to])continue;        get_rt(to,u);        siz[u]+=siz[to];        if(siz[to]>w[u])w[u] = siz[to];    }    w[u] = max(w[u],sum-siz[u]);    if(w[u]
         
          dis[y]-c[y].l;}int tot1,tot2;void push_up(int p1,int p2){    tot1 = 0;    while(p2!=p1)    {        p2 = c[p2].fa;        pu[++tot1] = p2;    }}void fill(int u){    pd[++tot2] = u;    for(int j=hed[u];j;j=e[j].nxt)    {        int to = e[j].to;        if(to==c[u].fa||mrk[to])continue;        fill(to);    }}void push_down(int p2){    tot2 = 0;fill(p2);    sort(pd+1,pd+1+tot2,cmp);}double slop(int a,int b){    return (double)(dp[a]-dp[b])/(dis[a]-dis[b]);}int fd(db k,vector
          
           &ve){ int l = 0,r = nd-1,ans = nd; while(l<=r) { int mid = (l+r)>>1; if(slop(pu[ve[mid]],pu[ve[mid+1]])
           

ve; for(;r<=tot2;r++) { while(l<=tot1&&dis[pu[l]]>=dis[pd[r]]-c[pd[r]].l) { while(ve.size()>=2&&slop(pu[l],pu[ve[nd]])>=slop(pu[ve[nd]],pu[ve[nd-1]])) ve.pop_back(); ve.push_back(l); l++; } if(!ve.size())continue; int u = pu[ve[fd(c[pd[r]].p,ve)]],v = pd[r]; dp[v] = min(dp[v],dp[u]-dis[u]*c[v].p+c[v].q); } for(r=tot2;dis[pd[r]]-c[pd[r]].l<=dis[p2]&&r>=1;r--) { int v = pd[r],u = p2; dp[v] = min(dp[v],dp[u]-dis[u]*c[v].p+c[v].q); } for(int j=hed[p2];j;j=e[j].nxt) { int to = e[j].to; if(to==c[p2].fa||mrk[to])continue; rt=0,sum=siz[to]; get_rt(to,0); cdq(to,rt); }}int main(){// freopen("1.in","r",stdin); n = rd(),t = rd();ll s; for(int f,i=2;i<=n;i++) { f = rd(),s = rd(),c[i].p = rd(),c[i].q = rd(),c[i].l = rd(); ae(f,i,s),ae(i,f,s); c[i].fa = f; } dfs(1,0); for(int i=2;i<=n;i++)c[i].q+=dis[i]*c[i].p; memset(dp,0x3f,sizeof(dp)); w[0] = inf;dp[1]=0; rt=0,sum=n; get_rt(1,0); cdq(1,rt); for(int i=2;i<=n;i++) printf("%lld\n",dp[i]); return 0;}