OAK - persistent oak - dummy solution not working

First of all I want to say that this is a pretty dumb question but I cannot make the brute force solution for the OAK problem.

My approach is this:

  1. read input
  2. make a tree with n+1 nodes (node 0 the root)
  3. make a DFS and keep for every node the dfsStart and dfsEnd as the positions in the DFS array (need this to know what nodes I have to 0 when a bird comes - query type 2)
  4. make a 2D array for states (p[][] - tree kept as parents - p[0] is the initial state)
  5. make a 2d array for total count of a subtree rooted at a specific node (c[][])
  6. at every query make the “next” state as a clone of the “state” from query
  7. if query is adding - then from the current node go up until the root or a branch gets broken and add the query count
  8. if a branch gets broken from that point until the root substract the weight existing on that subtree
  9. if query is bird type - then for the nodes starting from “dfsStart” to “dfsEnd” pf the query node zero the count on that node
  10. go up from the parent of the query node and substract the weight that was there before the bird arrived

I implemented this here https://www.codechef.com/viewsolution/14219647 but getting WA.
If anyone has some time to give me an example were I’m mistaken I’ll be forever grateful.

Thanks in advance.

Your code fails in this testcase:
1
5 4
0 5
1 3
2 1
2 1
3 1
0 1 5 1
1 1 4 1
2 1 3 1
3 1 2 2
Correct output:
0
0
3
0
Your Output:
0
0
3
2

@rishi_07 Can you explain the flaw in above approach??

I used almost same logic as @inseder, but got WA.

My code fails on your test case as well.

MY CODE

Thanks!

thanks @rishi_07

Bug - setting parent of a broken branch -1 before saving the value for going up

while (node > 0) {
    if (drop == 0) {
        if (c[next][node] + add > w[node]) {
            drop = node;
            sub = c[next][node];
            p[next][node] = -1;  // wrong
        } else {
            c[next][node] += add;
        }
    } else {
        c[next][node] -= sub;
    }
    node = p[next][node];        // wrong
}

fix - adding this line before the first if

int nextNode = p[nextState][node];

change the last line in
“node = nextNode;”