题目描述

棋如人生，落子无悔。步步思量，方能远航。

给定一棵 $n$ 个结点的树，第 $i$ 个结点有 $b_i$ 个棋子，且最多能放 $a_i$ 个棋子。现在有一个结点 $k$ 是根。每次操作你可以选择一个结点，将它的一个棋子，移到它的父亲上，需要满足它父亲的棋子数没有超过限制，然后需要最小化所有棋子到 $k$ 的距离和。

对 $k = 1, 2, \cdots, n$ 都求出答案。

输入格式

第一行包含一个正整数 $n$ 表示树的结点数量。

第二行包含 $n$ 个正整数，第 $i$ 个正整数表示第 $i$ 个结点上最多能放 $a_i$ 个棋子。

第三行包含 $n$ 个正整数，第 $i$ 个正整数表示第 $i$ 个结点上初始放了 $b_i$ 个棋子。

接下来 $n-1$ 行，每行两个数 $u,v$，表示树上的一条边。

输出格式

一行 $n$ 个整数，第 $i$ 个整数表示 $i$ 作为根时的答案。

输入输出样例 #1

输入 #1

3
6 2 10 
6 0 2 
1 2
2 3

输出 #1

2 6 0

输入输出样例 #2

输入 #2

5
7 6 2 1 10 
3 5 0 0 7 
1 2
2 3
1 4
4 5

输出 #2

10 12 20 14 9

输入输出样例 #3

输入 #3

见选手目录下的 𝚌𝚑𝚎𝚜𝚜/𝚌𝚑𝚎𝚜𝚜𝟹.𝚒𝚗。

输出 #3

见选手目录下的 𝚌𝚑𝚎𝚜𝚜/𝚌𝚑𝚎𝚜𝚜𝟹.𝚊𝚗𝚜。

说明/提示

对于所有数据满足：$1\le n\le 5\times 10^5$，$0 \le b_i \le a_i$，$1\le a_i\le 10^7$，为了避免答案爆 long long，将 $a_i$ 的范围开小了一点。

subtask 1（$1$ 分）：$b_i=0$；

subtask 2（$5$ 分）：$n\le 2000$；

subtask 3（$11$ 分）：$n\le 8000$；

subtask 4（$3$ 分）：链，保证 $\forall i\in [1, n-1]\cap \mathbb{Z}$，满足 $i$ 和 $i+1$ 有边；

subtask 5（$3$ 分）：菊花，保证 $\forall i\in [2, n]\cap \mathbb{Z}$，满足 $1$ 和 $i$ 有边；

subtask 6（$6$ 分）：保证树随机；

subtask 7（$16$ 分）：$a_i\le 5$；

subtask 8（$22$ 分）：$n\le 5\times 10^4$；

subtask 9（$16$ 分）：$n\le 10^5$；

subtask 10（$11$ 分）：$n\le 2\times 10^5$；

subtask 11（$5$ 分）：$n\le 3\times 10^5$；

subtask 12（$1$ 分）：无。

这里说明随机树的生成方式：对于结点 $i\in [2,n]$，在 $[1,i-1]$ 内等概率随机一个点 $p$，将 $i,p$ 连一条边。

#pragma GCC optimize("Ofast","inline","unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vector basic_string
#define endl '\n'
const int N=500009;
char buf[1<<22],*p1,*p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2)?EOF:*p1++)
inline int read(){
	int x=0,w=1;char ch=0;
	while((ch<'0'||ch>'9'))ch=getchar(),w=(ch=='-'?-w:w);
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch-'0'),ch=getchar();
	return x*w;
} 
char pbuf[1<<20], *pp=pbuf;
inline void push(const char &c) {
    if (pp - pbuf == 1<<20) fwrite(pbuf, 1, 1<<20, stdout), pp = pbuf;
    *pp++ = c;
}
inline void write(long long x,char tl=0){
	int sta[20],top=0;
	top=0;
	do{sta[top++]=x%10,x/=10;}while(x);
	while(top)push(sta[--top]+48);
	push(tl);
}
bool FL;
int n,tg,a[N],son[N],b[N],mxd[N],sz[N],dep[N],res[N];
vector<int> g[N],dp[N],pre[N],pre2[N];
int ep[N],epre[N],epre2[N];
array<int,3> ucp[N];
array<int,3> acp,bcp;
int pa[N<<1],apre[N<<1],apre2[N<<1];
int top,ub[N],utg[N],utg2[N],pb[N],bpre[N],bpre2[N];
vector<array<int,4> > ch;
int get(int u,int i=-1){
	if(i<0)i=(int)dp[u].size()-1;
	if(i<ep[u])return 0;
	return pre[u][i]-epre[u];
}
int get2(int u,int i=-1){
	if(i<0)i=(int)dp[u].size()-1;
	if(i<ep[u])return 0;
	return pre2[u][i]-epre2[u];
}
void clr(int u){
	for(int i=0;i<(int)dp[u].size();i++)
		if(i>=ep[u])pre[u][i]-=epre[u],pre2[u][i]-=epre2[u];
		else pre[u][i]=pre2[u][i]=0;
	ep[u]=epre[u]=epre2[u]=0;
}
void upd(int u,int f){
	int w=son[u];
	if(!w){
		dp[u].clear();dp[u].shrink_to_fit();
		dp[u].push_back(0);dp[u].push_back(b[u]);
		pre[u].clear();pre[u].shrink_to_fit();
		pre[u].push_back(0);pre[u].push_back(b[u]);
		pre2[u].clear();pre2[u].shrink_to_fit();
		pre2[u].push_back(0);pre2[u].push_back(b[u]*dep[u]);
		ep[u]=epre[u]=epre2[u]=0;
		return ;
	}
	swap(dp[u],dp[w]);
	swap(pre[u],pre[w]);
	swap(pre2[u],pre2[w]);
	swap(ep[u],ep[w]);
	swap(epre[u],epre[w]);
	swap(epre2[u],epre2[w]);
	for(int v:g[u])if(v!=f&&v!=w){
		clr(v);
		int t=mxd[w]-mxd[v];
		if(ep[u]>t){
			for(int i=ep[u];i<(int)dp[u].size();i++)
				pre[u][i]-=epre[u]-pre[u][t],pre2[u][i]-=epre2[u]-pre2[u][t];
			for(int i=t+1;i<ep[u];i++)
				pre[u][i]=pre[u][t],pre2[u][i]=pre2[u][t];
			epre[u]=pre[u][t];epre2[u]=pre2[u][t];
			ep[u]=t;
		}
		for(int i=0;i<(int)dp[v].size();i++)
			dp[u][i+t]+=dp[v][i],
			pre[u][i+t]+=pre[v][i],
			pre2[u][i+t]+=pre2[v][i];
	}
	int x=a[u]-b[u];
	for(int i=ep[u],sum=0,sum2=0;i<(int)dp[u].size();i++){
		int mn=min(dp[u][i],x);
		dp[u][i]-=mn;x-=mn;
		ep[u]=i;epre[u]+=mn;epre2[u]+=mn*(dep[u]+(int)dp[u].size()-i);
		if(!x)break;
	}
	dp[u].push_back(a[u]-x);
	pre[u].push_back(pre[u].back()+a[u]-x);
	pre2[u].push_back(pre2[u].back()+(a[u]-x)*dep[u]);
	// clr(u);
}
void dfs(int u,int f=0){
	mxd[u]=1;sz[u]=b[u];dep[u]=dep[f]+1;
	int w=0;
	for(int v:g[u])if(v!=f){
		dfs(v,u);
		sz[u]+=sz[v];
		mxd[u]=max(mxd[u],mxd[v]+1);
		if(mxd[v]>mxd[w])w=v;
	}
	son[u]=w;
	upd(u,f);
}
void unod(int u,int op,int d=0x3f3f3f3f){
	int t=max(1ll,(int)dp[u].size()-d);
	int reb=min(2*n,tg+(int)dp[u].size()-t+1);
	for(int i=tg;i<=reb+1;i++)ch.push_back({n+i,pa[i],apre[i],apre2[i]});
	if(reb>=acp[0]){
		for(int i=reb+1;i>acp[0];i--)pa[i]=apre[i]=apre2[i]=0;
		for(int i=acp[0];i>=tg;i--)apre[i]=apre[i+1]+pa[i],apre2[i]=apre2[i+1]+pa[i]*i;
		ch.push_back({-1,acp[0],acp[1],acp[2]});
		acp[0]=reb;acp[1]=acp[2]=0;
	}
	for(int i=t;i<(int)dp[u].size();i++)
		pa[tg+(int)dp[u].size()-i]+=dp[u][i]*op,
		apre[tg+(int)dp[u].size()-i]+=(get(u,i)-get(u,t-1))*op,
		apre2[tg+(int)dp[u].size()-i]+=(get2(u,i)-get2(u,t-1))*op+(get(u,i)-get(u,t-1))*(tg-dep[u]+1)*op;
}
int fs(int x){
	if(utg[x]>=acp[0])return bpre[x]-bcp[1];
	return bpre[x]-bcp[1]+apre[utg[x]+1]-acp[1];
}
int gs(int p,int x){
	if(p>top||x>=utg[p]+(int)dp[ub[p]].size())return x>acp[0]?0:apre[x]-acp[1];
	if(x>acp[0])return get(ub[p],utg[p]+(int)dp[ub[p]].size()-x)-ucp[p][1];
	return apre[x]-acp[1]+get(ub[p],utg[p]+(int)dp[ub[p]].size()-x)-ucp[p][1];
}
int F(){
	return (apre2[tg+1]-apre[tg+1]*tg)+(bpre2[top]-bpre[top]*tg)-(acp[2]-acp[1]*tg)-(bcp[2]-bcp[1]*tg);
}
int acc(int x){
	if(!x)return 0;
	int res=0;
	int l=bcp[0]-1,r=top;
	while(r>l){
		int mid=l+r+1>>1;
		if(fs(mid)<=x)l=mid;
		else r=mid-1;
	}
	if(l>=bcp[0]){
		int t=fs(l);
		x-=t;res+=t;
		ch.push_back({-1,acp[0],acp[1],acp[2]});
		ch.push_back({-2,bcp[0],bcp[1],bcp[2]});
		acp[0]=utg[l]+1;
		acp[1]=apre[acp[0]];
		acp[2]=apre2[acp[0]];
		bcp[0]=l+1;
		bcp[1]=bpre[l];
		bcp[2]=bpre2[l];
	}
	r=2*n,l=(bcp[0]>top?tg+1:utg[bcp[0]]+1);
	while(r>l){
		int mid=l+r+1>>1;
		if(gs(bcp[0],mid)>=x)l=mid;
		else r=mid-1;
	}
	// cout<<l-tg+1<<' '<<acp[0]-tg+1<<endl;
	if(bcp[0]>top||l>=utg[bcp[0]]+(int)dp[ub[bcp[0]]].size()){
		if(l>acp[0])return res;
		int t=min(x,gs(bcp[0],l));
		x-=t;res+=t;
		ch.push_back({-1,acp[0],acp[1],acp[2]});
		// cout<<t<<' '<<l-tg<<' '<<acp[0]<<endl;
		acp[0]=l;
		acp[1]+=t;
		acp[2]=apre2[acp[0]+1]+(acp[1]-apre[acp[0]+1])*(acp[0]);
		ch.push_back({n+acp[0],pa[acp[0]],apre[acp[0]],apre2[acp[0]]});
		pa[acp[0]]-=min(t,acp[1]-apre[acp[0]+1]);
	}else if(l>acp[0]){
		int t=min(x,gs(bcp[0],l));
		x-=t;res+=t;
		ch.push_back({-2,bcp[0],bcp[1],bcp[2]});
		ch.push_back({bcp[0],ucp[bcp[0]][0],ucp[bcp[0]][1],ucp[bcp[0]][2]});
		ucp[bcp[0]][0]=utg[bcp[0]]+(int)dp[ub[bcp[0]]].size()-l;
		ucp[bcp[0]][1]+=t;
		ucp[bcp[0]][2]=get2(ub[bcp[0]],ucp[bcp[0]][0]-1)+get(ub[bcp[0]],ucp[bcp[0]][0]-1)*(utg2[bcp[0]])
		+(ucp[bcp[0]][1]-get(ub[bcp[0]],ucp[bcp[0]][0]-1))*((int)dp[ub[bcp[0]]].size()-ucp[bcp[0]][0]+utg[bcp[0]]);
		bcp[1]+=t;
		bcp[2]=ucp[bcp[0]][2]+bpre2[bcp[0]-1];
	}else{
		int t=min(x,gs(bcp[0],l));
		x-=t;res+=t;
		ch.push_back({-1,acp[0],acp[1],acp[2]});
		ch.push_back({-2,bcp[0],bcp[1],bcp[2]});
		ch.push_back({bcp[0],ucp[bcp[0]][0],ucp[bcp[0]][1],ucp[bcp[0]][2]});
		int af=min(t-max(0ll,get(ub[bcp[0]],utg[bcp[0]]+(int)dp[ub[bcp[0]]].size()-l-1)-ucp[bcp[0]][1]),apre[l]-acp[1]),uf=t-af;
		acp[0]=l;
		acp[1]+=af;
		acp[2]=apre2[acp[0]+1]+(acp[1]-apre[acp[0]+1])*(acp[0]);
		ch.push_back({n+acp[0],pa[acp[0]],apre[acp[0]],apre2[acp[0]]});
		pa[acp[0]]-=min(af,acp[1]-apre[acp[0]+1]);
		ucp[bcp[0]][0]=utg[bcp[0]]+(int)dp[ub[bcp[0]]].size()-l;
		ucp[bcp[0]][1]+=uf;
		ucp[bcp[0]][2]=get2(ub[bcp[0]],ucp[bcp[0]][0]-1)+get(ub[bcp[0]],ucp[bcp[0]][0]-1)*(utg2[bcp[0]])
		+(ucp[bcp[0]][1]-get(ub[bcp[0]],ucp[bcp[0]][0]-1))*((int)dp[ub[bcp[0]]].size()-ucp[bcp[0]][0]+utg[bcp[0]]);
		bcp[1]+=uf;
		bcp[2]=ucp[bcp[0]][2]+bpre2[bcp[0]-1];
	}
	return res;
}
void rev(array<int,4> x){
	if(x[0]==-1)acp={x[1],x[2],x[3]};
	else if(x[0]==-2)bcp={x[1],x[2],x[3]};
	else if(x[0]<=n)ucp[x[0]]={x[1],x[2],x[3]};
	else pa[x[0]-n]=x[1],apre[x[0]-n]=x[2],apre2[x[0]-n]=x[3];
}
void dfs2(int u,int f=0){
	// cerr<<u<<' '<<F()<<endl;
	int d=0;
	int cdtop=(int)ch.size();
	for(int v:g[u])if(v!=son[u]&&v!=f)unod(v,1),d=max(d,mxd[v]);
	vector<array<int,3> > ptmp={};
	if(son[u]){
		apre[tg]=apre[tg+1];apre2[tg]=apre2[tg+1];
		int ctop=(int)ch.size();
		int t=acc(a[u]-b[u]);
		pa[tg]=b[u]+t;apre[tg]+=b[u]+t;apre2[tg]+=(b[u]+t)*tg;
		tg--;
		dfs2(son[u],u);
		tg++;
		while((int)ch.size()!=ctop)rev(ch.back()),ch.pop_back();
		upd(son[u],u);
		unod(son[u],1,d);
		for(int op=0;op<d;op++)
			ptmp.push_back({dp[son[u]].back(),pre[son[u]].back(),pre2[son[u]].back()}),
			dp[son[u]].pop_back(),pre[son[u]].pop_back(),pre2[son[u]].pop_back();
		top++;
		ub[top]=son[u];utg[top]=tg+d;utg2[top]=tg-dep[u];
		pb[top]=get(son[u]);
		bpre[top]=bpre[top-1]+get(son[u]);
		bpre2[top]=bpre2[top-1]+get2(son[u])+get(son[u])*(tg-dep[u]);
	}
	int ctop=(int)ch.size();
	int t=acc(a[u]-b[u]);
	res[u]=F();
	while((int)ch.size()!=ctop)rev(ch.back()),ch.pop_back();
	for(int v:g[u])if(v!=son[u]&&v!=f){
		int ctop=(int)ch.size();
		unod(v,-1);
		int ftop=(int)ch.size();
		apre[tg]=apre[tg+1],apre2[tg]=apre2[tg+1];
		int t=acc(a[u]-b[u]);
		pa[tg]=b[u]+t,apre[tg]+=b[u]+t,apre2[tg]+=(b[u]+t)*tg;
		tg--;
		dfs2(v,u);
		tg++;
		while((int)ch.size()!=ftop)rev(ch.back()),ch.pop_back();
		unod(v,1);
		while((int)ch.size()!=ctop)rev(ch.back()),ch.pop_back();
	}
	if(son[u]){
		while(!ptmp.empty())
			dp[son[u]].push_back(ptmp.back()[0]),
			pre[son[u]].push_back(ptmp.back()[1]),
			pre2[son[u]].push_back(ptmp.back()[2]),
			ptmp.pop_back();
		top--;
		unod(son[u],-1,d);
	}
	while((int)ch.size()!=cdtop)rev(ch.back()),ch.pop_back();
}
signed main(){
	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=n;i++)b[i]=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1);
	tg=n;bcp[0]=1;acp[0]=2*n;
	dfs2(1);
	for(int i=1;i<=n;i++)write(res[i],' ');
	return fwrite(pbuf, 1, pp - pbuf, stdout),0;
}