题目背景

题目描述

给定一棵 $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

提示

Idea：zhaohaikun，Solution：zhaohaikun，Code：zhaohaikun，Data：zhaohaikun

对于 $100\%$ 的数据，满足 $0 ≤ b_i ≤ a_i，1 ≤ a_i ≤ 10^7$，$1 ≤ n ≤ 5 × 10^5$。

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

subtask 2（5 分）：$n ≤ 2000$；

subtask 3（11 分）：$n ≤ 8000$；

subtask 4（3 分）：链，保证 $∀i ∈ [1, n − 1] ∩ Z$，满足 $i$ 和 $i + 1$ 有边；

subtask 5（3 分）：菊花，保证 $∀i ∈ [2, n] ∩ Z$，满足 $1$ 和 $i$ 有边；

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

subtask 7（16 分）：$a_i ≤ 5$；

subtask 8（22 分）：$n ≤ 5 × 10^4$；

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

subtask 10（11 分）：$n ≤ 2 × 10^5$；

subtask 11（5 分）：$n ≤ 3 × 10^5$；

subtask 12（1 分）：无。

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