#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
#include<unordered_map>
#define ll long long
using namespace std;
typedef vector<int> vecint;
typedef vector<ll> vecll;
typedef pair<ll,ll> Pair;
typedef pair<ll,ll> Pairl;
const ll MAXN=1e5+10;
const ll INF=4e18;
ll n,b[MAXN],fa[MAXN],pos[MAXN];
ll a[MAXN];vector <Pair> v[MAXN];
unordered_map <ll,unordered_map<ll,ll>> dis;
namespace tree
{
    ll MIN,R,S,siz[MAXN];bool vis[MAXN];
    void dfs(ll x,ll fa=0)
    {
        ll MAX=0;siz[x]=1;
        for(auto now:v[x])
        {
            ll y=now.first;
            if(y==fa||vis[y]) continue;
            dfs(y,x),siz[x]+=siz[y];
            MAX=max(MAX,siz[y]);
        }
        MAX=max(MAX,S-siz[x]);
        if(MAX<MIN) MIN=MAX,R=x;
    }
    void calc(ll x,ll fa=0,ll D=0)
    {
        dis[R][x]=D;
        for(auto now:v[x])
        {
            ll y=now.first;
            if(y==fa||vis[y]) continue;
            calc(y,x,D+now.second);
        }
    }
    void work(ll x)
    {
        vis[x]=true;calc(x);
        for(auto now:v[x])
        {
            ll y=now.first;
            if(vis[y]) continue;
            MIN=MAXN,S=siz[y],dfs(y);
            fa[R]=x,dfs(R),work(R);
        }
    }
    void init()
        {MIN=MAXN,S=n,dfs(1),dfs(R),work(R);}
}
inline bool cmp(ll x,ll y){return b[x]>b[y];}
struct node
{
    vector <Pairl> f;
    inline ll F(Pairl f,ll x)
        {return 1ll*f.first*x+f.second;}
    inline ll qry(ll x)
    {
        if(f.empty()) return INF;
        ll l=0,r=f.size()-1;
        while(l<r)
        {
            ll mid=(l+r)>>1;
            ll suma=F(f[mid],x);
            ll sumb=F(f[mid+1],x);
            (suma>=sumb)?l=mid+1:r=mid;
        }
        return F(f[l],x);
    }
    inline void upd(ll k,ll B)
    {
        if(!f.empty()&&f.back().first==k)
        {
            if(f.back().second>=B) return ;
            f.pop_back();
        }
        while(f.size()>=2&&f.back().first!=k)
        {
            int i=f.size();
            if((B-f[i-1].second)*(f[i-2].first-k)<=(B-f[i-2].second)*(f[i-1].first-k))
                f.pop_back();
            else break;
        }
        f.emplace_back(k,B);
    }
}t[MAXN];
inline ll qry(ll x)
{
    ll D=INF;
    for(ll p=x;p;p=fa[p])
        D=min(D,t[p].qry(dis[p][x]));
    return D;
}
inline void upd(ll x,ll D)
{
    for(ll p=x;p;p=fa[p])
        t[p].upd(b[x],D+a[x]+1ll*b[x]*dis[p][x]);
}
vecll travel(vecll A,vecint B,vecint U,vecint V,vecint W)
{
    n=A.size();
    for(ll i=0;i<n;++i)
        a[i+1]=A[i],b[i+1]=B[i];
    for(ll i=0;i<n-1;++i)
        v[U[i]+1].emplace_back(V[i]+1,W[i]),
        v[V[i]+1].emplace_back(U[i]+1,W[i]);
    tree::init();
    for(ll i=1;i<=n;++i) pos[i]=i;
    sort(pos+1,pos+n+1,cmp),upd(1,0);
    for(ll i=1;i<=n;++i)
    {
        if(b[pos[i]]>=b[1]) continue;
        ll Q=qry(pos[i]);upd(pos[i],Q);
    }
    vecll C;for(ll i=2;i<=n;++i)
        C.push_back(qry(i));return C;
}