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:
- read input
- make a tree with n+1 nodes (node 0 the root)
- 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)
- make a 2D array for states (p - tree kept as parents - p is the initial state)
- make a 2d array for total count of a subtree rooted at a specific node (c)
- at every query make the “next” state as a clone of the “state” from query
- if query is adding - then from the current node go up until the root or a branch gets broken and add the query count
- if a branch gets broken from that point until the root substract the weight existing on that subtree
- if query is bird type - then for the nodes starting from “dfsStart” to “dfsEnd” pf the query node zero the count on that node
- 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.