# Tree Traverse Help!(WA)

hello ,
solution:https://www.codechef.com/viewsolution/37007678
question :https://www.codechef.com/problems/CENS20F
@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
https://www.codechef.com/viewsolution/37008514
(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:

1. You donâ€™t reset vis between test cases
2. It will still time out on my case, because you donâ€™t actually mark the query node as visited
1 Like

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