#include<bits/stdc++.h>
// #include"grader.cpp"
using namespace std;
#define ll long long
const int MAXN=2e5+5;
const ll V=1e12,inf=1e18;
struct line{
	ll k,b;
	line(ll _k=-1,ll _b=0){k=_k,b=_b;}
	ll f(ll x){return k==-1?inf:k*x+b;}
};
struct lichaos{
int ls[MAXN*400],rs[MAXN*400],tot=0;line val[MAXN*400];
void insert(line L,int &id,ll l=0,ll r=V){
	if(L.k==-1||l>r) return;
	if(!id) id=++tot;
	ll mid=(l+r)>>1;
	if(L.f(mid)<val[id].f(mid)) swap(L,val[id]);
	if(L.k==-1) return;
	if(L.k>=val[id].k) insert(L,ls[id],l,mid);
	else insert(L,rs[id],mid+1,r);
}
ll ask(ll x,int id,ll l=0,ll r=V){
	if(id==0||val[id].k==-1) return inf;
	ll mid=(l+r)>>1;
	return min(val[id].f(x),x<=mid?ask(x,ls[id],l,mid)
		:ask(x,rs[id],mid+1,r));
}
}T;
vector<array<int,2> > edg[MAXN];
int siz[MAXN],msiz[MAXN],n,m,rt,mson;bool vis[MAXN];
ll a[MAXN],b[MAXN];
struct DAFEN{
vector<array<ll,2> > vec[MAXN];int rt[MAXN];
void get_size(int u,int fa){
	siz[u]=msiz[u]=1;
	for(auto e:edg[u]) if(e[0]!=fa&&!vis[e[0]]){
		get_size(e[0],u);
		siz[u]+=siz[e[0]];
		msiz[u]=max(msiz[u],siz[e[0]]);
	}
	msiz[u]=max(msiz[u],m-siz[u]);
	if(msiz[mson]>msiz[u]) mson=u;
}
void get_val(int u,int fa,int rt,ll w){
	vec[u].push_back({rt,w});
	siz[u]=msiz[u]=1;
	for(auto e:edg[u]) if(e[0]!=fa&&!vis[e[0]]){
		get_val(e[0],u,rt,w+e[1]);
		siz[u]+=siz[e[0]];
		msiz[u]=max(msiz[u],siz[e[0]]);
	}
	msiz[u]=max(msiz[u],m-siz[u]);
	if(msiz[mson]>msiz[u]) mson=u;
}
void build(int rt){
	vis[rt]=true;
	get_val(rt,-1,rt,0);
	for(auto e:edg[rt]) if(!vis[e[0]]){
		m=siz[e[0]];mson=n;
		get_size(e[0],rt);build(mson);
	}
}
void build(){
	msiz[n]=1e9;mson=n;m=n;
	get_size(0,-1);
	build(mson);
}
void insert(int x,ll v){
	for(auto r:vec[x]) T.insert(line(b[x],a[x]+v+b[x]*r[1]),rt[r[0]]);
}
ll query(int x){
	ll ans=1e18;
	for(auto r:vec[x]) ans=min(ans,T.ask(r[1],rt[r[0]]));
	return ans;
}
}dfz;

vector<ll> travel(vector<ll> A,vector<int> B,vector<int> U,
	vector<int> V,vector<int> W){
	n=A.size();
	for(int i=0;i<n;i++) a[i]=A[i],b[i]=B[i];
	for(int i=0;i<n-1;i++){
		edg[U[i]].push_back({V[i],W[i]});
		edg[V[i]].push_back({U[i],W[i]});
	}
	dfz.build();
	vector<int> id(n);
	for(int i=0;i<n;i++) id[i]=i;
	sort(id.begin(),id.end(),[&](int x,int y){
		return B[x]>B[y];
	});
	dfz.insert(0,0);
	for(int i=0;i<n;i++) dfz.insert(id[i],dfz.query(id[i]));
	vector<ll> ans(n-1);
	for(int i=0;i<n-1;i++) ans[i]=dfz.query(i+1);
	return ans;
}