#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef vector<int> vecint;
typedef vector<ll> vecll;
typedef pair<int,int> Pair;
typedef pair<ll,ll> Pairl;

const int MAXN=1e5+10;
const ll INF=4e18;

int n,b[MAXN],fa[MAXN],pos[MAXN];
ll a[MAXN];
vector <Pair> v[MAXN];
unordered_map <int,unordered_map<int,int>> dis;

namespace tree
{
    int MIN,R,S,siz[MAXN];
    bool vis[MAXN];
    void dfs(int x,int fa=0)
    {
        int MAX=0;siz[x]=1;
        for(auto now:v[x])
        {
            int 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(int x,int fa=0,ll D=0)
    {
        dis[R][x]=D;
        for(auto now:v[x])
        {
            int y=now.first;
            if(y==fa||vis[y]) continue;
            calc(y,x,D+now.second);
        }
    }
    void work(int x)
    {
        vis[x]=true;calc(x);
        for(auto now:v[x])
        {
            int 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(int x,int y)
    {return b[x]>b[y];}


struct node
{
    vector <Pairl> f;
    inline ll F(Pairl f,int x)
        {return f.first*x+f.second;}
    inline ll qry(ll x)
    {
        if(f.empty()) return INF;
        int l=0,r=f.size()-1;
        while(l<r)
        {
            int 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().second>=B)
            f.pop_back();
        if(f.empty()||f.back().first!=B)
            f.emplace_back(k,B);
    }
}t[MAXN];

inline ll qry(int x)
{
    ll D=INF;
    for(int p=x;p;p=fa[p])
        D=min(D,t[p].qry(dis[p][x]));
    return D;
}

inline void upd(int x,ll D)
{
    for(int 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(int i=0;i<n;++i)
        a[i+1]=A[i],b[i+1]=B[i];
    for(int 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(int i=1;i<=n;++i) pos[i]=i;
    sort(pos+1,pos+n+1,cmp);
    upd(1,0);
    for(int i=1;i<=n;++i)
    {
        if(b[pos[i]]>=b[1]) continue;
        cout<<"P:"<<pos[i]<<'\n';
        upd(pos[i],qry(pos[i]));
    }
    vecll C;
    for(int i=2;i<=n;++i)
        C.push_back(qry(i));
    return C;
}