C. Snowing
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
snowing approved for summer contest...

melting?

Conversation between jay_jayjay and alexlikemath007

You are given a tree with $$$n$$$ nodes, rooted at node $$$1$$$. The $$$i$$$-th node has a strength of $$$w_i$$$, meaning it can withstand a total of $$$w_i$$$ kgs of snow in its subtree. If a node has more than $$$w_i$$$ kgs of snow in its subtree, it is too heavy, and it will break.

At the end of every day, snow falls on every node. That is, $$$a_i$$$ kgs of snow fall on the $$$i$$$-th node. The snow falls instantaneously.

You may reinforce up to $$$k$$$ nodes, making them unbreakable. You wish to strengthen the tree such that the maximum possible amount of snow will gather on the tree before it breaks. The tree breaks once any of its nodes break. Snow that falls on the day that it breaks does not count.

For each $$$k = 0, 1, \dots, n-1,$$$ output the maximum weight of snow that the tree can gather.

Input

The first line contains one integer $$$n$$$ $$$(1 \leq n \leq 2 \cdot 10^5)$$$ — the number of nodes in the tree.

The second line contains $$$n$$$ integers $$$w_i$$$ $$$(1 \leq w_i \leq 5 \times 10^6)$$$ — the strength of the $$$i$$$'th node.

The third line contains $$$n$$$ integers $$$a_i$$$ $$$(1 \leq a_i \leq 5 \times 10^6)$$$ — the amount of snow that falls on the $$$i$$$'th node.

Each of the next $$$n-1$$$ lines contains two integers $$$u_j, v_j$$$ $$$(1 \leq u_j, v_j \leq n)$$$ – the nodes of the $$$j$$$'th edge. It is given that the edges form a tree.

—

Tests in subtasks are numbered from $$$1-20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1-20$$$ satisfy no additional constraints.

Output

For each value of $$$k$$$, print the integer $$$a$$$ — the amount of snow that will gather on the tree.

Examples
Input
3
30 4 5
5 1 3
1 2
1 3
Output
9
27
36
Input
5
100 50 2 3 4
1 1 1 2 3
1 2
1 3
2 4
2 5
Output
8
8
16
64
96
Note

Problem Idea: jay_jayjay

Problem Preparation: iframe

Occurrences: Novice C