Fruits on Tree
Problem Description

Given a complete rooted tree with N nodes numbered 1 to N. This tree has its leaves at the top and root at the bottom.
A complete tree is a tree which has all its leaf at the same level.

There are some fruits on every leaf of the tree and in order to get all the fruits you have to shake the tree any number of times.

But this tree is a little different than the rest it has following properties:

Every node has its capacity value that represents the number of fruits a node can hold at any moment.
Only one fruit Falls from each node to its parent node in one Shake.
If a number of fruits at a node is more than its Capacity then excess fruits(greater than Capacity) on that node at that instant will fall to the ground. This process happens instantaneously hence no shake required.
The tree is rooted at 1. You may assume that root is one level above ground so all fruits which fall from root lands on the ground.

You have to find the minimum number of shakes you have to perform such that all the fruits are on the ground.

Problem Constraints
1 <= N <= 105

1 <= A[i],B[i] <= 109

1 <= C[i][0],C[i][1] <= N

A[i] = 0 for non-leaf nodes

Initially, A[i] <= B[i]

Input Format
First argument is an integer array A of size N where A[i] denotes the number of fruits on ith node.

Second argument is an integer array B of size N where B[i] denotes the capacity of ith node.

Third argument is a 2D array C of size (N-1) x 2 denotes edges in the tree. There is an edge between nodes C[i][0] and C[i][1].

Output Format
Return an integer denoting the minimum number of shakes you have to perform such that all the fruits are on the ground.

Example Input
Input 1:

A = [0, 0, 0, 1, 1, 2]
B = [1, 1, 1, 1, 1, 2]
C = [
[1, 2]
[1, 3]
[2, 5]
[2, 6]
[3, 4]
]
Input 2:

A = [0, 0, 5, 5]
B = [10, 3, 10, 10]
C = [
[1, 2]
[2, 3]
[2, 4]
]

Example Output
Output 1:

4
Output 2:

9

Example Explanation
Explanation 1:

Given Tree:
6(2) 5(1) 4(1)
\ / /
2 3
\ /
1
Ground: ________________________
Leaf nodes are (6, 5, 4).
Now after one shake:
6(1) 5(0) 4(0)
\ / /
(1)2 3(1)
| \ /
v 1
Ground: 1_____________
Capacity of node 2 is 1, so the excess fruit i.e. will fall on the ground as shown.
After second shake:
6(0) 5(0) 4(0)
\ / /
(1)2 3(0)
\ /
1 (1)
Ground: 2_____________
This time there will be excess(i.e 2) fruit at node 1. So one fruit will fall to ground.
Now, 2 more shakes required to fall all 4 fruits on ground. So total shakes will be 4.

Explanation 2:

Given Tree:
4 3
\ /
2
|
1
Ground: ________________________
Leaf Nodes are 4 and 3. It will require 9 shakes such that all fruits fall on ground.