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?
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.
why would sorting of the nodes are required ? @anon73122115
@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 
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.
