Fruits On Tree :
Difficulty Level : Hard
Submissions : 487
Asked In :
Marks :10
: 9 | : 1
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 in which every leaf is at the same level of the tree.
In order to get all the fruits, you have to shake the tree any number of times.
This tree has the 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 the 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 is required.
The tree is rooted at 1. You may assume that the root is one level above the ground, so all fruits that fall from the root land 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.
The first line contains an integer N ($$$1 \le N le 10^5$$$) denoting the number of nodes in the tree.
The second line consists of N integers which denote the initial number of fruits in node $$$i$$$.
- (Current number of fruits in leaf node $$$1 \le A[i] \le 10^9$$$ ,for non leaf nodes $$$ A[i] = 0 $$$)
The third line consists of N integers which denote the capacity of node $$$i$$$. ( $$$1 \le A[i] \le 10^9$$$)
The next $$$N-1$$$ lines contain two integers $$$1 \le x,y \le N$$$, denoting a edge between node x and node y
Intially $$$A[i] \le B[i]$$$ $$$\forall$$$ $$$1\le i \le N$$$
Output an integer denoting the minimum number of shakes you have to perform such that all the fruits are on the ground.
6 0 0 0 1 1 2 1 1 1 1 1 2 1 2 1 3 2 5 2 6 3 4
4
4 0 0 5 5 10 3 10 10 1 2 2 3 2 4
9
7 0 0 0 1 1 1 1 4 2 2 1 1 1 1 1 2 1 3 2 4 2 5 3 6 3 7
6
