一开始居然脑子短路没有想到斜率优化……以后看到这种感觉跟凸包有关系，要求最值/要最优化的问题，可以考虑写个dp方程出来看看能不能斜率优化.
首先考虑链上，没有$l _v$的限制的情况，可以写出dp方程
这显然可以斜率优化，把$j$看成点$(d _j,\textrm{res} _j)$，那么使得答案最优的转移点一定在凸包上.
接下来考虑$l _v$的限制. 这个限制导致了一个问题，就是我们寻找转移点的时候，要在某个区间$[k,i)$上找，而不是在$[0,i)$上. 用二进制分组可以解决这个问题.
接下来考虑放到树上. 树造成了一个新的问题，如果我们直接做斜率优化的树形dp，就要支持在末端加入或者删除一个点，并维护凸包. 二进制分组理论上是只能加点的，否则摊还分析就会失效. 这里有一个简单的方法：只有在分裂了一个很大的块的时候，才会有很大的时间开销，因此我们可以随机地加入一些无用的点，就比较难卡掉了. 出题人好像没有考虑过这个算法，所以直接暴力删除也能过，还更快.
其实还有一些更靠谱的做法，比方说二进制分组靠谱的删除方法，类似替罪羊树的懒惰删除，但是我不想写. 或者树上问题转为链上问题的经典思路树剖，即在重链上二进制分组，重链之间直接暴力. 或者带根的点分治，晚点再研究.
有一个坑点是构建凸包的时候直接做叉积会爆long long
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
using namespace std;
const ele M=1<<19;
const ele size=M<<1;
const ele INF=1e18;
struct edge{
ele v;
edge *nxt;
}ep[maxn],*ecnt;
struct pt{
ele x,y;
}seq[maxn];
inline pt operator+(pt a,pt b){
return (pt){a.x+b.x,a.y+b.y};
}
inline pt operator-(pt a,pt b){
return (pt){a.x-b.x,a.y-b.y};
}
inline ele cross(pt a,pt b){
return a.x*b.y-a.y*b.x;
}
inline db test(pt a,pt b){
if (!a.x) return 0;
return (db)b.y/b.x-(db)a.y/a.x;
}
ele n,ty,tot,top,a[size],b[maxn],stk[maxn],f[maxn],s[maxn],p[maxn],q[maxn],l[maxn],res[maxn],d[maxn];
edge *h[maxn];
vector<pt> v[size];
inline void addedge(ele u,ele v){
edge *p=ecnt++;
p->v=v; p->nxt=h[u];
h[u]=p;
}
inline void build(vector<pt>&v,ele l,ele r){
v.clear();
for (int i=l; i<=r; ++i){
if (!seq[i].x && seq[i].y==INF) continue;
while (v.size()>1 && test(v[v.size()-1]-v[v.size()-2],seq[i]-v[v.size()-1])<1e-6)
v.pop_back();
v.push_back(seq[i]);
}
}
inline void upd(ele i,ele k){
ele L=1;
i+=M;
for (; i; i>>=1,L<<=1){
a[i]+=k;
if (a[i]==L){
ele j=i,k=i;
while (j<M) j<<=1,k=k<<1|1;
build(v[i],j-M,k-M);
}
}
}
inline void push(pt p){
seq[tot]=p;
upd(tot++,1);
}
inline void push(ele i){
push((pt){d[i],res[i]});
if (rand()&1) push((pt){0,INF});
}
inline void pop(){
upd(--tot,-1);
}
inline ele calc(pt v,ele d,ele p,ele q){
return (d-v.x)*p+q+v.y;
}
inline ele qry(vector<pt>&v,ele d,ele p,ele q){
if (!v.size()) return INF;
ele L=-1,R=v.size()-1;
while (R-L>1){
ele mid=(L+R)>>1;
if (calc(v[mid],d,p,q)>=calc(v[mid+1],d,p,q)) L=mid; else R=mid;
}
return calc(v[R],d,p,q);
}
inline ele qry(ele l,ele r,ele d,ele p,ele q){
ele ans=1e18;
for (l=l+M-1,r=r+M+1; l^r^1; l>>=1,r>>=1){
if (~l&1) ans=min(ans,qry(v[l^1],d,p,q));
if (r&1) ans=min(ans,qry(v[r^1],d,p,q));
}
return ans;
}
void dfs(ele i){
if (i){
ele L=-1,R=top-1;
while (R-L>1){
ele mid=(L+R)>>1;
if (d[i]-d[stk[mid]]<=l[i]) R=mid; else L=mid;
}
res[i]=qry(b[stk[R]],tot-1,d[i],p[i],q[i]);
}
stk[top++]=i;
b[i]=tot;
push(i);
for (edge *j=h[i]; j; j=j->nxt) d[j->v]=d[i]+s[j->v],dfs(j->v);
--top;
do{
pop();
}
while (seq[tot].x!=d[i] || seq[tot].y!=res[i]);
}
int main(){
scanf("%lld%lld",&n,&ty);
ecnt=ep; memset(h,0,sizeof(h));
for (int i=1; i<n; ++i)
scanf("%lld%lld%lld%lld%lld",f+i,s+i,p+i,q+i,l+i),--f[i],addedge(f[i],i);
d[0]=0; top=0; tot=1;
dfs(0);
for (int i=1; i<n; ++i) printf("%lld\n",res[i]);
return 0;
}