#define _CRT_SECURE_NO_WARNINGS 1	

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
const int N=100005,M=N*40;

#define ll long long
const ll INF=900000000000000007ll,U=100000000000ll;

struct edge{
	int v,w;
};

struct line{
	ll k,b;

	inline ll operator()(ll x)const{
		return k*x+b;
	}
};

int n,up[N],sz[N],c[N],h[N];
bool vis[N];
ll a[N],b[N],ds[25][N];
vector<edge> g[N];

void dfs1(int x,int fa,int k,ll d){
	sz[x]=1;
	ds[k][x]=d;

	for(edge e:g[x]) if(e.v!=fa&&!vis[e.v]){
		dfs1(e.v,x,k,d+e.w);
		sz[x]+=sz[e.v];
	}
}

void dfs2(int x,int fa,int tot,int &rt){
	c[x]=tot-sz[x];

	for(edge e:g[x]) if(e.v!=fa&&!vis[e.v]){
		dfs2(e.v,x,tot,rt);
		c[x]=max(c[x],sz[e.v]);
	}

	if(!rt||c[x]<c[rt]) rt=x;
}

void build(int x,int k){
	h[x]=k;
	vis[x]=true;
	dfs1(x,0,k,0);

	for(edge e:g[x]) if(!vis[e.v]){
		int rt=0;
		//dfs2(e.v,x,sz[e.v],rt);
		rt=e.v;
		up[rt]=x;
		build(rt,k+1);
	}
}

int c1,c2;
int w[M],ls[M],rs[M],rt[N],id[N];
line f[M];

#define mid (l+r>>1)

void update(int &x,ll l,ll r,int v){
	if(!x){
		x=++c1;
		w[x]=v;
		return ;
	}

	if(f[w[x]](mid)>f[v](mid)) swap(w[x],v);
	if(l<r){
		if(f[w[x]](l)>f[v](l)) update(ls[x],l,mid,v);
		if(f[w[x]](r)>f[v](r)) update(rs[x],mid+1,r,v);
	}
}

ll query(int x,ll l,ll r,ll p){
	if(!p) return INF;
	if(l<r){
		if(p<=mid) return min(f[w[x]](p),query(ls[x],l,mid,p));
		else return min(f[w[x]](p),query(rs[x],mid+1,r,p));
	}else return f[w[x]](p);
}

void update(int x,ll v){
	for(int i=x;i;i=up[i]){
		f[++c2]={b[x],v+b[x]*ds[h[i]][x]};
		update(rt[i],0,U,c2);
	}
}

ll query(int x){
	ll res=INF;

	for(int i=x;i;i=up[i])
		res=min(res,query(rt[i],0,U,ds[h[i]][x]));

	return res;
}

vector<ll> travel(vector<ll> A,vector<int> B,vector<int> U,vector<int> V,vector<int> W){
	int i;
	vector<ll> ans;
	n=A.size();

	for(i=1;i<=n;i++) a[i]=A[i-1],b[i]=B[i-1],id[i]=i;
	for(i=0;i<n-1;i++){
		g[U[i]+1].push_back({V[i]+1,W[i]});
		g[V[i]+1].push_back({U[i]+1,W[i]});
	}

	build(1,0);
	f[0]={0,INF};
	update(1,a[1]);
	sort(id+1,id+n+1,[](int x,int y){return b[x]>b[y];});

	for(i=1;i<=n;i++) if(b[i]<b[1])
		update(id[i],query(id[i])+a[id[i]]);

	for(i=2;i<=n;i++) ans.push_back(query(i));

	return ans;
}