With this input, following my solution, we get:
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.
Shouldn’t k be only 1(1 subtree with min value (negative sum) removed) or 0(no subtree removed) to minimize ‘X*k’ factor ?
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
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 
.
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
Can some one give same kind of problems for practice
I also thought of the same thing. Maybe using Segment Trees to Update values will get it accepted …
I haven’t tried that yet …
What am I missing here?
#include <bits/stdc++.h>
#define ll long long
#define INF (int)1E9 + 5
using namespace std;
const int N = 1e5 + 5;
ll sum[N];
vector graph[N];
ll a[N];
ll dfs(ll v, ll cost, ll prev){
if(sum[v] == INF){
sum[v] = a[v];
for(auto nei : graph[v]){
if(nei != prev){
sum[v] += dfs(nei,cost,v);
}
}
}
return max(sum[v], cost);
}
int main(){
int t,n,s,d;
ll x;
cin >> t;
while(t--){
cin >> n >> x;
for(int i = 1; i <= N; i++){
sum[i] = INF;
graph[i].clear();
}
for(int i = 1; i <= n; i++){
cin >> a[i];
}
for(int i = 1; i <= n-1; i++){
cin >> s >> d;
graph[s].push_back(d);
}
cout << dfs(1,-x,0) << "\n";
}
}
After reading this thread, I changed the graph to undirected, (although I’m still not sure why a tree should be an undirected graph)
I’ve also tried to build several testcases on my own, but they all seem to give the correct output.
Any help would be greatly appreciated.
why do we need to store the TREE as undirected?
i tried using undirected , it gives WA .
can someone explain , why it fails ?
https://www.codechef.com/viewsolution/24047123
I did not quite understand this line, undirected is a term associated with graphs and here we are given a tree (so it’s more of a parent-child relation here) …
we are given a list of edges present between two nodes and that’s it, the parent-child relation is NOT given, we don’t know which node is parent of which node and which node is child of which node so first we need to FIND THAT relationship between nodes !!! (we have been told that 1 is the root and its value is the first element of the value array) so we have to start from root and find the parent-child relation of each node. function “parents” exactly does that (have a look at my solution, the link is provided below)
Then recursively we will find out whether to include that node (and its subtree) or remove that node (and its subtree).
link to my solution : CodeChef: Practical coding for everyone
I hope my answer was helpful …
Hi there,
I didn’t understand that in the editorial the summation of weights of nodes is given as dp
and I found no traces of Dynamic Programming in this problem
When we call the dfs function we basically iterate over whole subtree of tha node again and again so where is DP used in this problem
please help me understand
PS - I’m very noob at cp don’t even know dp:cry:
can anyone please explain why the o/p of the following test case is -1 instead of -2,
test case :
1
5 2
1 1 -1 -1 -1
1 2
2 3
4 1
4 5It helped thanks.
It “why do we need to store the TREE as undirected?” meant
why should we store a to b and b to a (a and b being nodes).
Now i understand we don’t have parent-child relationship here.
I guess no one can explain it and the fact that the question had wrong test cases.???!!!
and obviously it was a wrong question
We remove the subtree of 4.
Total value of remaining tree = (1 + 1 + (-1)) = 2 - 1 = 1;
x = 2;
So profit = 1 - 2 = -1
No, it wasn’t. But ya, there are some tricky test cases and the question is tricky too…
oh ya!!! got it!!! wonderful question !!!
if thats the case then any of the nodes can act like a root node?