题目大意：给你一颗$n$个点的有根树，相邻两个点之间有距离，我们可以从$x$乘车到$x$的祖先，费用为$dis\times P[x]+Q[x]$，问你除根以外每个点到根的最小花费。
数据范围：$n≤10^6$。
此题我们显然$dp$，列出方程为$f[x]=min\{f[y]+dis(x,y)\times P[x]+Q[x]\}$，其中$y$为$x$的祖先。
不难看出可能是一个斜率优化的式子，我们往下推推
设$i$是$j$的祖先，且从$i$出转移比从$j$处转移劣，不难列出：
$f[i]+dis(i,x)P[x]+Q[x]>f[j]+dis(j,x)P[x]+Q[x]$
化简化简，令$D_i$表示从根到$i$的距离，继续移项化简
$f[i]-f[j]>P[x]((D_x-D_j)-(D_x-D_i))$
$f[i]-f[j]>P[x](D_i-D_j)$
$\dfrac{f[i]-f[j]}{D_i-D_j}<P[x]$（注意大于符号变成小于，因为$D_i<D_j$，重要！，我被坑了）
考虑到$P$随着点深度递增，于是就可以快乐斜率优化了。
不过这题需要在树上转移，当遍历完一个子树后，我们要把单调队列恢复，恢复操作显然可以用可持久化线段树来搞。
其实不用这么复杂，考虑到只存在移动队头，移动队尾&在队尾加一个数的操作，我们只需要记录下以前的队头/尾的情况，还有被覆盖的数原先是啥，就可以在常数时间内恢复回去。
然而这么做的话无法保证移动队头尾的次数是线性的（我们搞一个链+链底菊花树），所以在找队头和队尾时，需要用二分。
于是时间复杂度就变成$O(n\log\ n)$了，二分的常数很小，问题不大。
（我比较懒写了暴力移动的，二分的话自己脑补吧qwq）
#include<bits/stdc++.h>
#define M 1000005
#define L long long
using namespace std; struct edge{L u,v,next;}e[M]={}; L head[M]={},use=;
void add(L x,L y,L z){use++;e[use].u=y;e[use].v=z;e[use].next=head[x];head[x]=use;}
L n,f[M]={},P[M]={},Q[M]={},dis[M]={},q[M]={},h=,t=; double slope(L i,L j){return .*(f[i]-f[j])/(dis[i]-dis[j]);} void dfs(L x,L D){
L H=h,T=t;
while(h<t&&P[x]>slope(q[h],q[h+])) h++;
f[x]=f[q[h]]+((dis[x]=D)-dis[q[h]])*P[x]+Q[x];
while(h<t&&slope(q[t-],q[t])>slope(q[t],x)) t--;
L lastT=q[++t]; q[t]=x;
for(L i=head[x];i;i=e[i].next) dfs(e[i].u,D+e[i].v);
q[t]=lastT; h=H; t=T;
} main(){
scanf("%lld",&n);
for(L i=;i<=n;i++){
L fa,dis; scanf("%lld%lld%lld%lld",&fa,&dis,P+i,Q+i);
add(fa,i,dis);
}
q[t=]=; for(L i=head[];i;i=e[i].next) dfs(e[i].u,e[i].v);
for(L i=;i<=n;i++) printf("%lld\n",f[i]);
}