#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
#define int long long
using ll=long long;
const ll inf=1e18;
ll n, a[N], b[N];
ll sz[N], vis[N], rt, S, mn, ft[N], fw[N];
vector<pair<ll, ll> > e[N];
void findrt(ll u, ll f) {
	sz[u]=1;
	ll res=0;
	for(auto t:e[u]) {
		int v=t.first; 
		if(v==f||vis[v]) continue ;
		findrt(v, u);
		sz[u]+=sz[v];
		res=max(res, sz[v]);
	}
	res=max(res, S-sz[u]);
	if(res<mn) mn=res, rt=u;
}
ll dis[N];
void pdfs(int u, int fa) {
	for(auto t:e[u]) {
		ll v=t.first, w=t.second;
		if(v==fa||vis[v]) continue ;
		dis[v]=dis[u]+w;
		pdfs(v, u);
	}
}
void dfs(int u) {
	vis[u]=1;
	sz[u]=S+1;
	dis[u]=0; pdfs(u, 0);
	for(auto t:e[u]) {
		ll v=t.first, w=t.second;
		if(!vis[v]) {
			S=sz[v]; rt=0; mn=inf;
			findrt(v, 0);
			ft[rt]=u; fw[rt]=dis[rt];
			dfs(rt);
		} 
	}
}
struct Node{
	ll x, y;
};
long double K(Node A, Node B) {
	return 1.0L*(A.y-B.y)/(A.x-B.x);
}
struct TB{
	vector<Node> A;
	void Ins(Node p) {
		if(!A.empty()&&A.back().x==p.x) {
			p.y=min(p.y, A.back().y);
			A.pop_back();
		}
		while(A.size()>1&&K(A[A.size()-1], A[A.size()-2])<=K(A[A.size()-1], p)) A.pop_back();
		A.push_back(p);
	}
	ll qry(ll k) {
		if(A.empty()) return inf;
		k=-k;
		ll L=1, R=A.size()-1, now=0;
		while(L<=R) {
			ll mid=L+R>>1;
			if(K(A[mid], A[mid-1])>k) now=mid, L=mid+1;
			else R=mid-1;
		}
		return A[now].y-k*A[now].x;
	}
} tb[N];
ll f[N];
ll get(int u) {
	if(u==1) return 0; ll res=inf;
	for(ll i=u, d=0; i; d+=fw[i], i=ft[i]) {
		res=min(res, tb[i].qry(d));
	}
	return res;
}
void change(int u) {
	f[u]=get(u);
//	cout<<f[u]<<"\n";
	for(ll i=u, d=0; i; d+=fw[i], i=ft[i]) {
		tb[i].Ins(Node{b[u], f[u]+a[u]+b[u]*d});
	}
}

int p[N];
#undef int
vector<long long> travel(vector<long long> A, vector<int> B, vector<int> U,
 vector<int> V, vector<int> W) {
	n=A.size();
	for(int i=1; i<=n; i++)
		a[i]=A[i-1], b[i]=B[i-1];
	for(int i=1; i<n; i++) {
		ll u=U[i-1]+1, v=V[i-1]+1, w=W[i-1];
		e[u].push_back({v, w});
		e[v].push_back({u, w});
	}
	S=n; mn=inf; rt=0;
	findrt(1, 0);
	dfs(rt);
	for(int i=1; i<=n; i++) p[i]=i;
	sort(p+1, p+1+n, [&](ll x, ll y){
		return b[x]>b[y];
	});
	for(int i=1; i<=n; i++) {
		change(p[i]);
	}
	vector<ll> res(n-1);
	for(int i=2; i<=n; i++) res[i-2]=get(i);
	return res;
}
/*
int main() {
	vector<ll> res=travel({10, 5, 13, 4, 3}, {10, 7, 5, 9, 1}, {1, 0, 3, 2}, {0, 2, 2, 4}, {1, 5, 10, 3});
	for(ll v:res) cout<<v<<" "; 
}
*/
/*
5
10 5 13 4 3
10 7 5 9 1
1 0 1
0 2 5
3 2 10
2 4 3
*/