hello ,
Can anyone please help me find bug in my code
solution:CodeChef: Practical coding for everyone
question :CENS20F Problem - CodeChef
@ssrivastava990, @galencolin
1 Like
No, we are missing some edge cases
Do you know any such edge case ?
Nope
1 Like
Can you please give a test case I am not able to get you
First of all, code like this is so confusing… a local reference variable that’s passed down through the whole tree instead of just returning the value from the DFS. But that’s not the issue.
Did you read the constraints? They say 0 \leq A_i \leq 10^9. So this heuristic you have on lines 38 and 52, if(a[q]==0)return ;, won’t work (and there’s a simple case that makes it O(nq) anyway).
1 Like
can you elaborate on why if( a[q]==0) won’t work ?
but in O(n*q) will equal to one time dfs isn’t ??
What’s the purpose of including that line?
1 Like
without that line it is giving TLE, I am using that line if a subtree is previously be computed i.e. value a[i] ==0 then no need to compute that subtree again and just return
Yes. But because of the constraints, a number can be 0 initially, meaning you’ll falsely think that a subtree has been computed when it actually hasn’t been.
Also, even with that heuristic, a test case that looks like this:
where the tree is rooted at the red vertex, there are (10^5 - 1) black chains of length 2, and every query is on the red vertex, makes your program O(nq), but it just happened to not be included in the tests because codechef is OP
3 Likes
@galencolin
I have taken care of that special already “zero” case as well, but still my solution gets WA 
CodeChef: Practical coding for everyone
(I even stress-tested with the AC solutions, and there seems to be no testcase where my code fails)
yes , agreed that above given example if 1 st query as red node then for the first query i will visit the entire tree and mark all the node as visited ,so for the next subsequent query on red node or any node on the tree I will not traverse that node since the node is already traversed in first query so it will be amortized complexity will still be O(tree)
https://www.codechef.com/viewsolution/37008488
That actually makes it worse in multiple ways:
- You don’t reset
visbetween test cases - It will still time out on my case, because you don’t actually mark the query node as visited
1 Like
Please fix your spacing, that’s absolutely unreadable
Thank you @galencolin for solving my silly doubts and helping me with optimisations.
can you please explain what is making a diff by not marking query node as visited since would just add an simple O(1) operation per query since all the subtree was makred visited as in
why TLE FOR (O(1)2(10^5-1)+ 2*(10^5))??
1 Like
Let’s look at the exact code you have:
void dfs_even(int q,int par)
{
if(vis[q])return ;
for(auto i:e[q])
{
if(i!=par)
{
ans+=a[i];
dfs_even(i,q);
vis[i]=true;
a[i]=0;
}
}
}
You have if(vis[q]) return;, which notably won’t affect the query node since it’s not set, but affects all the children. However, each time, you still go through all even children, and only return after having gone through it. So it’ll consider all of the even children each query.
The way to fix this is to set the query node to visited. But this could be bad - you still want to consider the node’s value in a later query as it could be greater than 0. So the fix is to change it to something like this:
if (vis[q]) {
ans += a[q];
a[q] = 0;
return;
}
which both does the pruning and is still correct, since you may want to look at that specific node but don’t need to consider its children.
2 Likes
GREAT !!! THANK YOU VERY MUCH 
