I need help please. I used the same logic as the editorialist but I have WA CodeChef: Practical coding for everyone
1 Like
Try adding the followings at the top:
import sys
sys.setrecursionlimit(10**5)
3 Likes
Here is my easy to understand ac code,you have to sum the value of nodes of a given subtree and check whether its value is less than -x or not,if it is replace it with -x
//subtree removal
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
vectoradj[100005];
ll a[100005];
ll dp[100005];
ll visited[100005];
ll n,x;
void dfs(ll u)
{
visited[u]=true;
dp[u]=a[u];
ll sum=a[u];
for(ll child : adj[u])
{
if(!visited[child])
{
dfs(child);
sum+=dp[child];
}
}
if(sum<-x)
dp[u]=-x;
else
dp[u]=sum;
}
int main()
{
int t;
cin >> t;
while(t–)
{
cin >> n >> x;
memset(a,0,sizeof(a));
memset(dp,0,sizeof(dp));
memset(visited,false,sizeof(visited));
memset(adj,0,sizeof(adj));
for(int i=1;i<=n;i++)
cin >> a[i];
ll u,v;
for(int i=1;i<=n-1;i++)
{
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1);
cout << dp[1] << endl;
}
return 0;
}
5 Likes
Didn’t check your logic but Why TLE?
Hint:
Argument Passing to Functions
- Pass by Value
- Pass by Reference
3 Likes
Hi,
One thing that is still confusing me is the number of operations ‘k’. Our objective is to minimize the value “X*k” and hence k should only take values 0 or 1 (depending on whether we remove any subtree or not). As per my solution, I found the maximum value of remaining nodes by subtracting each subtree sum from whole tree sum i.e. max(sum(root)- sum[i](for all subtrees)).
I am not able to see any case left in this approach but still getting the wrong answer.
My solution: https://www.codechef.com/viewsolution/23943487
1 Like
Why we need to add an edge from v to u if we have initialized an edge from u to v already?
If we don’t add an edge from v to u I got wrong answer why is it so? Please explain.
3 Likes
Oh thanks a lot.
I understand now. I used to feel that vectors, like arrays, are sent by reference but instead vectors are sent by value and a copy is generated. Due to recursive nature of function, sending by value leads to TLE. After sending by reference, it works correctly.
2 Likes
Check the Sample Input again.
1
3 5
1 -5 -10
1 2
2 3
1 Like
still wrong answer
is there any problem in declaring the list and dict global ?
1 Like
I guess you can’t understand the question.
The question states that you can remove ANY number of subtrees, which are ‘k’ and your profit at the end is the (sum of values of the nodes left in tree - x * k).
You can remove more than one subtree also to maximize the profit. You have to take some test cases and understand that.
Hope this helps 
1 Like
dats what i have done .
u can check my soln.
1 Like
How do we know about the count (k) of deletions? I didn’t understand the the mathematical equation?
1 Like
With this input, following my solution, we get:
- whole tree sum[1] = -14
- sum of subtree rooted at 2, sum[2] = -15
- sum of subtree rooted at 3, sum[3] = -10
Now, max sum we get by trying removing every subtree, (sum[1]-sum[i], for each i<=N), is 1.
now, since k = 1, answer will be 1-5*1, i.e. -4 which is expected.
I’m not sure what kind of case seem to be missing.
1 Like
Shouldn’t k be only 1(1 subtree with min value (negative sum) removed) or 0(no subtree removed) to minimize ‘X*k’ factor ?
2 Likes
Try by using scanf while taking input.
I wrote a very similar function, only used a uni directional graph instead of a bidirectional graph. Code :
#include<bits/stdc++.h>
using namespace std;
// Creating an adjacency list
array <vector, 100001> adj_list;
int T, N, X;
vector values;
// Function to find the maximum profit
long long int FindMax(int n){
// Finding number of neighbours
int no_neighs = adj_list[n].size();
long long int value = values[n- 1];
// Non terminating condition
long long int total_profit = value, removing_profit = -1 * X;
// Iterating through all the neighbours for induvidual profits
for(int i = 0; i < no_neighs; ++i){
int neigh = adj_list[n][i];
long long int profit = FindMax(neigh);
total_profit += profit;
}
long long int ans = max(removing_profit, total_profit);
return ans;
}
int main(){
int temp;
int u, v;
cin >> T;
// Creating a vector to store the values
while(T--){
cin >> N >> X;
// Taking in the input values to be stored in the tree nodes
for(int i = 0; i < N; ++i){
cin >> temp;
values.push_back(temp);
}
// Getting connecting values
for(int i = 0; i < N - 1; ++i){
cin >> u >> v;
// Adding it to the adjacency list
adj_list[u].push_back(v);
}
// Finding maximum profit
long long int max_profit = FindMax(1);
cout << max_profit << endl;
// Clearing the vector of values and the adjacency list
values.clear();
// Clearing the adjacency list
for(int i = 0; i < N; ++i){
adj_list[i].clear();
}
}
return 0;
}
Can anyone spot if there are any problems because I kept getting wrong answer
1 Like
Of course not,
The profit is calculated at the END of the operations.
To be more clear, work with this test case.
1
3 1
4 -12 -13
1 2
1 3
The answer should be 2.
In the first step we remove the subtree of position 3.
Total value = -8, number of times operation performed = 1.
Now we remove the subtree of position 2.
Total value = 4, number of times operation performed = 2.
Therefore,
Profit = Total value - (number of time operation performed * x)
= 4 - (2 * 1)
= 2
Answer equals 2.
On the other hand, according to what you are doing, the answer will be -1.
Hope this helps .
1 Like
At each point you can either drop the subtree or not. Since we are doing it recursively, the value of -X adds up at each step if it’s optimal.
Drawing a Recurrence Tree will be helpful.
if u used directed graph then its wrong
Inputs are not like
u v then u is parent and v is child
it can be other way around. Hence assume it as undirected graph
3 Likes
Can some one give same kind of problems for practice
1 Like