I am stuck in this SPOJ question. Can anyone please point out as to where I am going wrong ? I am not even getting the sample test cases correct..
Here's the link to the question :
http://www.spoj.com/problems/ADDAP/
And here's my solution for it. I am using BFS to detect the level of the nodes(I am pushing -1 into the queue after completion of each level & -1 here detects the completion of a level), but unfortunately not getting the correct answer.
You seem to be assuming that all the edges in the input are directed from parent to child.
Even if you fix that your complexity is O(N^2), so it won't pass.
Note that if you have updates (u, x, y) and (u, x', y') you can combine them into (u, x + x', y + y'). So you can group the updates for one node into a single update.
Also note that applying (u, x, y) means adding x to solution[u], and then applying (c, x + y, y) for all children c of u.
Using those two (though not completely naively) you should be able to solve the problem in a single dfs.