I wrote a solution but got stuck since I couldn’t see what went wrong here. Can someone provide a simple test case so that I realize my mistake here?
My approach: Calculate the depth of each node using a BFS (considering root to be at depth 0), and then create a list of each node corresponding to it’s depth, so that the list nodeAtDepth[i] tells us what nodes are there at depth i.
Then, for each query V, consider all nodes k at distance depth[V] + 2y and add A[k] to A[V], and set A[k] to 0. If I find a depth which I’ve already visited before, all of those values must have been set to 0 and so I can discard it.
Consider this case
1
8 1
1 1 1 1 1 1 1 1
1 2
2 3
3 4
4 7
2 5
5 6
6 8
5
If two nodes are at different even depths it doesn’t necessarily mean that one is in the subtree of the other.
Your output - 1 1 1 1 3 1 0 0
Correct output - 1 1 1 1 2 1 1 0
I was coding segment tree along with euler tour. Only Update function was left when I realised one doesn’t need it.
“Things to watch out for” Did got one TLE due to this.
Thanks brother , I was missing a Q.pop() operation when I was using continue statement But after correcting it also I am getting correct answer on your test case but WA during submission. Can you now tell me some test cases where my solution is failing . Thanks in advance. https://www.codechef.com/viewsolution/37007493
Actually your approach is not correct. We have to transfer the values of nodes at even distance to the source node “present in that subtree”.
But according to your approach you are transfering values of all nodes whose depth is even from that node, so there may be some nodes which can not be present in that subtree.
Can anybody explain me this…It is written in the editorial that “if visited[vertex][1] == 1, all the nodes at odd distance from the current vertex are zero. So there is no need to go further.” but, aren’t we interested in the nodes at even distance from the vertex so why no need to go further?
