I tried to solve the https://www.codechef.com/APRIL19B/problems/SUBREM using the following algorithm, but got WA.
Solution
Can someone help me whats wrong with the algo.
At every node I maintain 3 values
- first: number of cut operations performed in it’s subtree
- second: total sum of the nodes in the subtree after the cut operation has been performed.
- third: total sum of the nodes in the subtree when the cut operation has not been performed. This value is used to decide whether I cut this particular node itself, so that all the child cut operations can be converged to 1 by cutting all their parents.
- My final answer to the problem is: second - first *X
Logic to cut/not cut is if sum of the subtree < 0 and |sum|>X, then I cut.
Excerpt from my solution
ilpair compute(int u, vector<vector<int> > &adj, vector<int> &weights, int X) {
long total=0;
ilpair ans;
// initialise the ans to 000
for(auto v:adj[u]) {
pair<int, lpair > p = compute(v,adj,weights,X);
ans.first+= p.first;
ans.sec+=p.sec;
ans.third+=p.third;
}
ans.sec+=weights[u];
ans.third+=weights[u];
if(ans.sec<0&&abs(ans.third)>X) {
// remove
ans.first=1;
ans.sec=0;
}
return ans;
}