题目描述

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

给定一棵 $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$ 作为根时的答案。

3
6 2 10 
6 0 2 
1 2
2 3

2 6 0

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

10 12 20 14 9

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

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

提示

对于所有数据满足：$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$ 连一条边。

bonus

感谢 @_LHF_ 同学将本题的空间复杂度优化到了 $O(n)$，加强版链接：https://www.luogu.com.cn/problem/P11690。