感谢 Fz 的题解！
首先这题有一个 DP 式子，
\[f_i = d_i \times p_i + q_i +\min(-d_j\times p_i+f_j) \]明显是斜率优化的形式。
但对于 \(u\) 有贡献的只有离他较近的若干个祖先。
这里就有几个做法；
- 点分
- 树剖，u 到某个祖先可以剖为 若干条重链的前缀 + 一条重链的中间一段，然后丢在重链上处理。
- 在 dfs 的过程中，维护一个可撤销的单调栈（用来维护凸包）
- 一种巧妙的做法：首先 dfs ，在每个点 dfs 出去的时候记上时间戳，可以得到出栈序。dfs DP 的时候，维护一个线段树套李超树（或者单调栈维护凸包也行），每次到 u 时，查询的就是 [ u 的出栈序 到 那个祖先的出栈序 ] 这一段区间的点，进行转移。
这种方法也许在处理其他题（从上到下的查询？）时也有用。
贺来的代码
#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define int long long
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 200005
#define N 4000005
int n;
vector<int>e[maxn];
int k[maxn],b[maxn],cnt,rt[maxn<<2];
inline int f(int id,int x){return k[id]*x+b[id];}
int tag[N],ls[N],rs[N];
void upd(int&p,int l,int r,int x)
{
if(!p)p=++cnt;
if(!tag[p])return tag[p]=x,void();
int mid=l+r>>1;
if(f(x,mid)<f(tag[p],mid))swap(x,tag[p]);
if(l<r) k[x]<k[tag[p]]?upd(rs[p],mid+1,r,x):upd(ls[p],l,mid,x);
}
int qry(int p,int l,int r,int x)
{
if(!p)return 1e18;
int mid=l+r>>1;
return min(f(tag[p],x),x<=mid?qry(ls[p],l,mid,x):qry(rs[p],mid+1,r,x));
}
void modify(int p,int l,int r,int x,int v)
{
upd(rt[p],0,1e6,v);
if(l==r)return;
int mid=l+r>>1;
x<=mid?modify(p<<1,l,mid,x,v):modify(p<<1|1,mid+1,r,x,v);
}
int ask(int p,int l,int r,int ql,int qr,int v)
{
if(l>=ql&&r<=qr)return qry(rt[p],0,1e6,v);
int mid=l+r>>1,res=1e18;
if(ql<=mid)res=min(res,ask(p<<1,l,mid,ql,qr,v));
if(qr>mid)res=min(res,ask(p<<1|1,mid+1,r,ql,qr,v));
return res;
}
int o[maxn],idx;
void getO(int u){
for(auto v:e[u])getO(v);
o[u]=++idx;
}
int s[maxn],p[maxn],q[maxn],l[maxn],fa[maxn];
int dp[maxn],dis[maxn],top,id[maxn];
void dfs(int u)
{
k[u]=-dis[top],b[u]=dp[u];
id[top]=u;
modify(1,1,n,o[u],u);
for(auto v:e[u]){
++top,dis[top]=dis[top-1]+s[v];
int anc=id[lower_bound(dis,dis+top,dis[top]-l[v])-dis];
dp[v]=ask(1,1,n,o[v],o[anc],p[v]);
dp[v]=dp[v]+dis[top]*p[v]+q[v];
dfs(v);
--top;
}
}
signed main()
{
n=read(),read();
For(i,2,n){
fa[i]=read(),s[i]=read(),p[i]=read(),q[i]=read(),l[i]=read();
e[fa[i]].pb(i);
}
getO(1);
dfs(1);
For(i,2,n)printf("%lld\n",dp[i]);
return 0;
}