Fruits On Tree DSA Problem Solution

Fruits On Tree DSA Problem Solution

by

In this post, we are going to solve Fruits On Tree DSA Problem from MediaNet Online assessment. Let’s have a look at the problem statement first and then try to solve the problem.

Fruits On Tree DSA Problem Statement

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.

Input

The first line contains an integer N (

1≤Nle105) 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≤A[i]≤109 

    ,for non leaf nodes A[i]=0 

    )

The third line consists of N integers which denote the capacity of node

i. (

1≤A[i]≤109)

The next

N−1 lines contain two integers

1≤x,y≤N, denoting a edge between node x and node y

Intially

A[i]≤B[i]

∀

1≤i≤N

Output

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

Examples
Input
6
0 0 0 1 1 2
1 1 1 1 1 2
1 2
1 3
2 5
2 6
3 4
Output
4
Input
4
0 0 5 5
10 3 10 10
1 2
2 3
2 4
Output
9
Input
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
Output
6

Fruits On Tree DSA Problem Solution in C++

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
long long n, fruit[N], limit[N], d[N], ans[N];
vector<vector<int>> g;

void dfs(int src, int par)
{
long long sum = 0, maxi = 0;
bool isLeaf = 1;
for(auto child : g[src])
{
if(child == par)
continue;
dfs(child, src);

isLeaf = 0;
if(ans[child] > maxi)
maxi = ans[child];

d[src] = max(d[src], d[child] + 1);
sum += (ans[child] - d[child]);
}

if(isLeaf)
ans[src] = fruit[src];
else
ans[src] = maxi + min(limit[src], sum - (maxi - d[src]));
}

int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
cin >> fruit[i];

for(int i = 1; i <= n; i++)
cin >> limit[i];

g.resize(n + 1);
for(int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}

dfs(1, 0);
cout << ans[1] << endl;


return 0;
}

Leave a Comment