题目链接

题意：给出一棵树，\(1\) 号点为根，边上有边权。

每个点有两个参数 \(p_i,q_i\)

如果你想从 \(i\) 号点到与其距离为 \(d\) 的 \(j\) 号点，那么你需花费 \(d \times p_i+q_i\)。

对于每个 \(i \in [2,n]\)，求出：假设你站在 \(i\) 号点，到达 \(1\) 号点的最小花费。

\(1 \leq n \leq 10^6\)

树上斜率优化

dfs 求出 \(i\) 到根节点的路径长度为 \(d_i\)。

朴素的 \(dp\) 非常容易。设 \(dp_i\) 表示到达 \(i\) 号点的最小花费。那么显然

\[dp_i=\min{dp_j+(d_i-d_j) \times p_i+q_i}
\]

假设 \(j\) 在 \(k\) 的下方，那么 \(j\) 比 \(k\) 更优当且仅当：

\[dp_j+(d_i-d_j) \times p_i+q_i<dp_k+(d_i-d_k) \times p_i+q_i
\]

\[dp_j-d_j \times p_i<dp_k-d_k \times p_i
\]

\[dp_j-dp_k<(d_j-d_k) \times p_i
\]

\[\frac{dp_j-dp_k}{d_j-d_k}<p_i
\]

开个队列维护 \(i\) 的祖先的点组成的下凸包，然后在队列里二分斜率就可以了。

/*
Contest: -
Problem: P3994
Author: tzc_wk
Time: 2020.5.29
*/
#include <bits/stdc++.h>
using namespace std;
#define fi            first
#define se            second
#define fz(i,a,b)    for(int i=a;i<=b;i++)
#define fd(i,a,b)    for(int i=a;i>=b;i--)
#define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define all(a)        a.begin(),a.end()
#define giveup(...) return printf(__VA_ARGS__),0;
#define fill0(a)    memset(a,0,sizeof(a))
#define fill1(a)    memset(a,-1,sizeof(a))
#define fillbig(a)    memset(a,0x3f,sizeof(a))
#define fillsmall(a) memset(a,0xcf,sizeof(a))
#define mask(a)        (1ll<<(a))
#define maskx(a,x)    ((a)<<(x))
#define _bit(a,x)    (((a)>>(x))&1)
#define _sz(a)        ((int)(a).size())
#define filei(a)    freopen(a,"r",stdin);
#define fileo(a)    freopen(a,"w",stdout);
#define fileio(a)     freopen(a".in","r",stdin);freopen(a".out","w",stdout)
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define put(x)        putchar(x)
#define eoln        put('\n')
#define space        put(' ')
#define y1            y1010101010101
#define y0            y0101010101010
#define int long long
typedef pair<int,int> pii;
inline int read(){
    int x=0,neg=1;char c=getchar();
    while(!isdigit(c)){
        if(c=='-')  neg=-1;
        c=getchar();
    }
    while(isdigit(c))   x=x*10+c-'0',c=getchar();
    return x*neg;
}
inline int qpow(int x,int e,int _MOD){
    int ans=1;
    while(e){
        if(e&1) ans=ans*x%_MOD;
        x=x*x%_MOD;
        e>>=1;
    }
    return ans;
}
int n=read();
vector<pii> g[1000005];
int p[1000005],q[1000005],dep[1000005],dp[1000005];
int dq[1000005],hd=1,tl=0;
inline double sl(int j,int k){
    return 1.0*(dp[k]-dp[j])/(dep[k]-dep[j]);
}
inline int bsearch(double slo){
    if(hd==tl)  return dq[hd];
    int l=hd,r=tl-1,ans=tl;
    while(l<=r){
        int mid=(l+r)>>1;
        if(sl(dq[mid],dq[mid+1])>=slo)  ans=mid,r=mid-1;
        else                            l=mid+1;
    }
    return dq[ans];
}
inline void dfs(int x){
    int y=bsearch(p[x]);
    int curhd=hd,curtl=tl;
    dp[x]=dp[y]+(dep[x]-dep[y])*p[x]+q[x];
    while(hd<tl&&sl(dq[tl],dq[tl-1])>sl(dq[tl],x))  tl--;
    int curq=dq[++tl];
    dq[tl]=x;
    foreach(it,g[x]){
        int z=it->first,s=it->second;
        dep[z]=dep[x]+s;
        dfs(z);
    }
    hd=curhd,dq[tl]=curq,tl=curtl;
}
signed main(){
    fz(i,2,n){
        int f=read(),s=read();
        p[i]=read(),q[i]=read();
        g[f].push_back({i,s});
    }
    dfs(1);
    fz(i,2,n)   cout<<dp[i]<<endl;
    return 0;
}