树上斜率优化
#include<cstdio>
#include<algorithm>
using namespace std;
int cnt,n,top,v[100005],w[100005],last[100005],Dep[100005],Last_ID[100005],ID[100005];
long long F[100005];
struct node1{
long long k,b;
}stack[100005],Last_val[100005];
struct node{
int to,next,val;
}e[200005];
void add(int a,int b,int c){
e[++cnt].to=b;
e[cnt].next=last[a];
e[cnt].val=c;
last[a]=cnt;
}
double check(node1 a,node1 b){
return ((double)a.b-b.b)/(b.k-a.k);
}
void insert(node1 line,int x){
int L=1,R=top;
if (top<=1 || check(stack[top],stack[top-1])<check(stack[top],line)) ID[x]=top+1;
else{
while (L<R){
int mid=(L+R)>>1;
double X;
if (mid==1) X=-1ll<<60;
else X=check(stack[mid],stack[mid-1]);
double Y=check(line,stack[mid]);
if (X>Y) R=mid;
else L=mid+1;
}
ID[x]=L;
}
Last_ID[x]=top;
Last_val[x]=stack[ID[x]];
top=ID[x];
stack[ID[x]]=line;
}
void solve(int x){
int L=1,R=top;
while (L<R){
int mid=(L+R)>>1;
double l,r;
if (mid==1) l=-1ll<<60;
else l=check(stack[mid],stack[mid-1]);
if (mid==top) r=1ll<<60;
else r=check(stack[mid],stack[mid+1]);
if (v[x]>=l && v[x]<=r){
L=mid;
break;
}
else if (v[x]<l) R=mid-1;
else L=mid+1;
}
F[x]=stack[L].k*v[x]+stack[L].b;
F[x]+=1ll*Dep[x]*v[x]+w[x];
//for (int i=1; i<=top; i++)
// F[x]=min(F[x],-1ll*Dep[stack[i]]*v[x]+F[stack[i]]);
// printf("ans:%d %d %lld
",x,-Dep[x],F[x]);
insert((node1){-Dep[x],F[x]},x);
}
void dfs(int x,int fa,int dep){
Dep[x]=dep;
solve(x);
for (int i=last[x]; i; i=e[i].next){
int V=e[i].to;
if (V==fa) continue;
dfs(V,x,dep+e[i].val);
}
stack[ID[x]]=Last_val[x];
top=Last_ID[x];
}
int main(){
scanf("%d",&n);
for (int i=1; i<n; i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
for (int i=2; i<=n; i++) scanf("%d%d",&w[i],&v[i]);
dfs(1,0,0);
for (int i=2; i<=n; i++)
printf("%lld ",F[i]);
return 0;
}