#include <bits/stdc++.h>
#define double long double
#define int long long
#ifdef zhr_debug
#define debug printf
#else
void debug(const char* s,...){}
#endif
using namespace std;
const int inf=1000000000000000000ll;
void freopen(string file){freopen((file+".in").c_str(),"r",stdin);freopen((file+".out").c_str(),"w",stdout);}
int n;
int a[100020];
int b[100020];
struct edge
{
	int to,val;
	edge(int to=0,int val=0):to(to),val(val){}
};
vector<edge> e[100020];
int fa[100020][20];
int dep[100020];
int dis[100020];
int sz[100020];
bool vis[100020];
void findrt(int x,int f,int all,int &rt)
{
	sz[x]=1;
	int mx=0;
	for(edge v:e[x])
	{
		if(vis[v.to] || v.to==f) continue;
		findrt(v.to,x,all,rt);
		sz[x]+=sz[v.to];
		mx=max(mx,sz[v.to]);
	}
	mx=max(mx,all-sz[x]);
	if(mx<=n/2) rt=x;
}
int top[100020];
void dfs1(int x,int f)
{
	fa[x][0]=f;for(int i=1;i<=17;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
	dep[x]=dep[f]+1;
	for(edge v:e[x])
	{
		if(v.to==f) continue;
		dis[v.to]=dis[x]+v.val;
		dfs1(v.to,x);
	}
}
int getlca(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=17;i>=0;i--) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
	if(x==y) return x;
	for(int i=17;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
int getdis(int x,int y){return dis[x]+dis[y]-2*dis[getlca(x,y)];}
void dfs2(int x,int f,int all)
{
	findrt(x,0,all,x);
	findrt(x,0,all,x);
	debug("dfs2(%lld)\n",x);
	top[x]=f;
	vis[x]=true;
	for(edge v:e[x])
	{
		if(vis[v.to] || v.to==f) continue;
		dfs2(v.to,x,sz[v.to]);
	}
}
int o[100020];
int dp[100020];
struct node
{
	int x,y;
	node(int x=0,int y=0):x(x),y(y){}
};
double slope(node a,node b){return 1.0L*(a.y-b.y)/(a.x-b.x);}
struct ConvexHull
{
	vector<node> hull;
	void insert(node a)
	{
		if(hull.size() && hull.back().x==a.x)
		{
			a.y=min(a.y,hull.back().y);
			hull.pop_back();
		}
		while(hull.size()>1 && slope(hull[hull.size()-1],hull[hull.size()-2])<=slope(hull[hull.size()-1],a)) hull.pop_back();
		hull.push_back(a);
	}
	int query(int k)
	{
		if(hull.empty()) return inf;
		k=-k;
		static int l,r,mid,res;
		l=1;r=hull.size()-1;res=0;
		while(l<=r)
		{
			mid=(l+r)>>1;
			if(slope(hull[mid],hull[mid-1])>k) res=mid,l=mid+1;
			else r=mid-1;
		}
		return hull[res].y-hull[res].x*k;
	}
};
ConvexHull hull[100020];
void work(int x)
{
	debug("work(%lld)\n",x);
	if(x==1) dp[x]=0;
	else
	{
		dp[x]=inf;
		for(int xx=x;xx;xx=top[xx])
		{
			dp[x]=min(dp[x],hull[xx].query(getdis(x,xx)));
			debug("query : %lld=%lld\n",getdis(x,xx),hull[xx].query(getdis(x,xx)));
		}
	}
	debug("dp[%lld]=%lld\n",x,dp[x]);
	for(int xx=x;xx;xx=top[xx])
	{
		hull[xx].insert(node(b[x],dp[x]+a[x]+b[x]*getdis(x,xx)));
		debug("insert : (%lld,%lld+%lld+%lld*%lld)\n",b[x],dp[x],a[x],b[x],getdis(x,xx));
	}
}
vector<int> travel(vector<int> A,vector<signed> B,vector<signed> U,vector<signed> V,vector<signed> W)
{
	n=A.size();
	for(int i=0;i<n;i++) a[i+1]=A[i];
	for(int i=0;i<n;i++) b[i+1]=B[i];
	for(int i=0;i<n-1;i++)
	{
		e[U[i]+1].push_back(edge(V[i]+1,W[i]));
		e[V[i]+1].push_back(edge(U[i]+1,W[i]));
	}
	dfs1(1,0);
	dfs2(1,0,n);
	debug("top : ");for(int i=1;i<=n;i++) debug("%lld ",top[i]);debug("\n");
	debug("dis : ");for(int i=1;i<=n;i++) debug("%lld ",dis[i]);debug("\n");
	for(int i=1;i<=n;i++) o[i]=i;
	sort(o+1,o+n+1,[](int x,int y){return b[x]>b[y];});
//	for(int i=1;i<=n;i++) work(o[i]);
	vector<int> ans;
//	for(int i=2,tmp;i<=n;i++)
//	{
//		tmp=inf;
//		for(int xx=i;xx;xx=top[xx]) tmp=min(tmp,hull[xx].query(getdis(i,xx)));
//		ans.push_back(tmp);
//	}
	return ans;
}
//signed main()
//{
//	vector<int> res=travel({10,5,13,4,3},{10,7,5,9,1},{1,0,3,2},{0,2,2,4},{1,5,10,3});
//	for(int x:res) printf("%lld ",x);
//}