#include <bits/stdc++.h>
#define rep(i,a,b) for (ll i=(a); i<=(b); ++i)
#define all(x) begin(x),end(x)
#define siz(x) int((x).size())
using namespace std;
using ll = long long;
using vi = vector<ll>;
using ii = pair<ll,ll>;
using vi32 = vector<int>;

const ll INF = 1e18;
const ll N = 1e5+3;
ll n, a[N], b[N];
vector<ii> adj[N];

struct cht {
    struct line {
        ll a, b;
        ll operator () (ll x) { return ll(a)*x+b; }
    };
    vector<line> v;
    bool ok(line x, line y, line z) {
        return __int128_t(x.a-y.a)*(z.b-x.b) <= __int128_t(x.a-z.a) * (y.b-x.b);
    }
    void insert(line x) {
        while (siz(v)>=2 && ok(end(v)[-2], end(v)[-1], x)) v.pop_back();
        v.push_back(x);
    }
    ll get(ll x) {
        ll l=0, r=siz(v)-2, m;
        while (l<=r) {
            m=(l+r)/2;
            if (v[m](x) > v[m+1](x)) l=m+1;
            else r=m-1;
        }
        return empty(v) ? INF : v[l](x);
    }
};

namespace cd {
    ll sub[N], lev[N], dist[N][18], par[N]; bool erased[N];
    void calc_sub(ll s, ll e) {
        sub[s] = 1;
        for (auto [u,w] : adj[s]) if(u!=e&&!erased[u]) calc_sub(u,s), sub[s] += sub[u];
    }
    ll find_cent(ll s, ll e, ll S) {
        for (auto [u,w] : adj[s]) if(u!=e&&!erased[u])
            if (S/2 < sub[u]) return find_cent(u,s,S);
        return s;
    }
    void dfs(ll s, ll e, ll L, ll d) {
        dist[s][lev[s]-L] = d;
        for (auto [u,w] : adj[s]) if(u!=e&&!erased[u]) dfs(u,s,L,d+w);
    }
    void build(ll s=1, ll e=0) {
        calc_sub(s,e), s=find_cent(s,e,sub[s]);
        lev[s]=lev[e]+1, par[s]=e, erased[s]=true;
        for (auto [u,w] : adj[s]) if(u!=e&&!erased[u]) build(u,s);
        for (auto [u,w] : adj[s]) if(u!=e&&!erased[u]) dfs(u,s,lev[s],w);
        erased[s]=false;
    }
}

cht ds[N];

ll query(ll x) {
    ll res=INF;
    for (ll i=0, c=x; c; i++, c=cd::par[c]) {
        res = min(res, ds[c].get(cd::dist[x][i]));
    }
    return res;
}
void update(ll x, ll y) {
    for (ll i=0, c=x; c; i++, c=cd::par[c]) {
        ll A = a[x];
        ll B = y + b[x] + cd::dist[x][i] * A;
        if (B >= INF) continue;
        ds[c].insert({A,B});
    }
}

vi travel(vi A, vi32 B, vi32 U, vi32 V, vi32 W) {
    n = A.size();
    rep(i,1,n) {
        a[i] = B[i-1];
        b[i] = A[i-1];
    }
    rep(i,0,n-2) {
        adj[U[i]+1].push_back({V[i]+1, W[i]});
        adj[V[i]+1].push_back({U[i]+1, W[i]});
    }
    
    cd::build();
    
    vi vertices(n-1); iota(all(vertices),2);
    sort(all(vertices),[](ll x, ll y){ return a[x] > a[y]; });
    
    vi res(n-1);
    update(1,0); for (auto s : vertices) update(s, query(s));
    
    rep(i,2,n) res[i-2] = query(i);
    return res;
}