Edge Deletion Pratilipi Hiring Challenge

Question :
Edge Deletion

You are given a tree of N nodes and an integer K. Each node contains an integer stored in it. You are required to delete the minimum number of edges (possibly 0) from the tree such that after deletion of that edges the sum of every individual tree formed is less than or equal to K

Input Format

  • First line : Two space-separated integer N and K.
  • Next line : N space-separated integers where an i_{th} integer denotes the value stored in the i_{th} node
  • Next N - 1 lines : Two space-separated integers U and V which denotes there is an edge between node U and V

Output Format
Print an integer answer to the question

Constraints

1 \leq N \leq 10^5
1 \leq K \leq 10^9
1 \leq value stored in every node \leq K
1 \leq U, V \leq N

Sample Input

7 8
4 3 2 7 2 1 6
1 2
1 3
1 4
3 5
3 6
4 7

Sample Output
3

Explaination

How to approach this problem?

Can you provide the link?

https://www.hackerearth.com/challenges/hiring/pratilipi-fullstack-hiring-2019/

Contest over.

Do dfs, inside your dfs function make a vector and whenever visiting a node push all the children into the vector.
After the dfs is over for a node , sort the vector and now check add the value of the number in
the vector to the value of the node till it is less than the value of the k, once it becomes large increase the count value as much the remaining elements in the vector.


ll dfs(int u)
{
    ll count1=0;
    visited[u]=1;
    vector<int> v;
    for(auto i = G[u].begin();i!=G[u].end();i++)
    {

        if(!visited[*i])
        {
          count1+= dfs(*i);
           v.pb(A[*i]);
        }
    }
    sort(v.begin(),v.end());
    for(int j=0;j<v.size();j++)
    {
        if(A[u]+v[j]<k) {A[u]=A[u]+v[j];
        
        }
        else { count1 += v.size()-j; break;}
    }
     return count1;
}
``` if you don;t understand tell me.
I  am not sure if this code will work for every cases as i have not submitted it. But i think this should work.
1 Like

TestCase :
k:9
weight: [ 1,4,4,1,1,1,1]
edges:
1 2
1 3
2 4
2 5
3 6
3 7
I think, as per your solution, you would delete 4 edges, though solution can be obtained by deleting 3 edges ( namely 3,6,7 ). Let me know if I am wrong.

answer should be 1 …

1 Like

why would sorting of the nodes are required ? @shubham97361

@harshraj22.If we disconnect edge 1 from the test case ,The formed 2 trees have the sum<k.In your case the answer will be 1.My logic also failing in this case,Will update the post.

1 Like

Because we should pick the minimum of all the children that will ensure that the deletion of edges will be minimum.
consider this case:
4 6
1 4 2 2
1 2
1 3
1 4

I participated in that challenge. I wrote similar type of code using same logic. It got accepted :grinning:

1 Like

Bro if you have second programming question from that challenge , please post it

There are three types of people namely A, B, and C. An Infinite
number of people are standing outside a restaurant but the
restaurant can accommodate only n people at a time. Also, the
restaurant has a special type of arrangement where the seats are
arranged in a row structure. The people have some rules in
which no A type people will sit with another A type people and the
same goes for B type people. The C type people do not have any
preference but the restaurant will allow at most m of C type people
at a time.

You are given that the capacity of the restaurant is n and the
maximum allowed number of people are m, find out the number
of ways in which they can be seated in the restaurant modulo 10

Input format

First line: An integer n denoting the capacity of restaurants
Next line: An integer m denoting the number of C allowed

Output format

Print a single Integer denoting the number of ways to be seated
mod 107

Constraints

1<=n <=1000
1<=m<=n

Sample Input
2
1
Sample Output
6
Explanation

The possible arrangements are as below

AB

CB

CA

AC

BA

BC
@gpatel3

Have you solved it. Please share the approach

It can be solved using DP,as the constraints are weak.