#include<bits/stdc++.h>
#define reg register
#define int long long
inline bool cmin(reg int &x,reg int y){return x>y?x=y,1:0;}
inline bool cmax(reg int &x,reg int y){return x<y?x=y,1:0;}
const int N=1e6+10,INF=4e18;
int n,a[N],b[N],mx[N],sz[N],S,rt,vis[N],id[N];
std::vector<std::pair<int,int>> anc[N],G[N];
void findrt(reg int u,reg int fa=0){
    sz[u]=1,mx[u]=0;
    for (auto [v,w]:G[u]) if (v!=fa&&!vis[v]) findrt(v,u),sz[u]+=sz[v],cmax(mx[u],sz[v]);
    cmax(mx[u],S-sz[u]); if (mx[rt]>mx[u]) rt=u;
}
void dfs(reg int u,reg int fa=0,reg int d=0){
    anc[u].push_back({rt,d}),sz[u]=1;
    for (auto [v,w]:G[u]) if (v!=fa&&!vis[v]) dfs(v,u,d+w),sz[u]+=sz[v];
}
void dc(reg int u){
    vis[u]=1,dfs(u); assert(u==rt);
    for (auto [v,w]:G[u]) if (!vis[v]) S=sz[v],rt=0,findrt(v),dc(rt);
}
struct Node{int x,y;};
inline long double K(reg Node A,reg Node B){return 1.0L*(A.y-B.y)/(A.x-B.x);}
struct DS{
    std::vector<Node> A;
    inline void ins(reg Node p){
        if (!A.empty()&&A.back().x==p.x) return cmin(A.back().y,p.y),void();
        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);
    }
    inline int qry(reg int k){
        if (A.empty()) return INF; k=-k; 
        reg int L=1,R=A.size()-1,now=0;
        // std::cerr<<"qry ";
        // for (auto [x,y]:A) std::cerr<<x<<" "<<y<<" "; std::cerr<<"\n";
        while (L<=R){
            reg int 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;
        // reg int res=INF;
        // for (auto [x,y]:A) cmin(res,y-x*k); return res;
    }
}s[N];
inline int getdis(reg int u){
    if (u==1) return 0; reg int res=INF;
    for (auto [r,d]:anc[u]) cmin(res,s[r].qry(d)); return res;
}
void upd(reg int u){
    reg int now=getdis(u);
    // std::cerr<<"<< "<<u<<" "<<now<<"\n";
    for (auto [r,d]:anc[u]) s[r].ins({b[u],now+a[u]+d*b[u]});
}
#undef int
std::vector<long long> travel(std::vector<long long> A,
        std::vector<int> B, std::vector<int> U, std::vector<int> V, std::vector<int> W){
    #define int long long
    n=A.size();
    for (reg int i=1;i<=n;i++) a[i]=A[i-1],b[i]=B[i-1];
    for (reg int i=0;i+1<n;i++) G[U[i]+1].push_back({V[i]+1,W[i]}),G[V[i]+1].push_back({U[i]+1,W[i]});
    mx[0]=1e9,S=n,findrt(1),dc(rt); //assert(0);
    for (reg int i=1;i<=n;i++) id[i]=i;
    std::sort(id+1,id+n+1,[](reg int x,reg int y){return b[x]>b[y];});
    for (reg int i=1;i<=n;i++) upd(id[i]);
    std::vector<int> res(n-1);
    for (reg int i=2;i<=n;i++) res[i-2]=getdis(i); 
    return res;
}