Hello, the contest Abacus’17 has just finished. Can somebody tell how to solve the problem, Geek Tree.

Can someone tell the solution for this problem too : https://www.codechef.com/ABCS2017/problems/ABCS05

@tihorsharma

In this problem,try drawing a matrix to come up with a solution.

You will observe a pattern.

If u still can’t figure it out, tell me and I’ll tell u the full solution.

This u can do easily bu using a dfs and BIT or segment tree.Basically as u go into a branch during dfs u update the node value in BIT.Then u do a search for all values in the range [s-k,s+k] in the ancestors where “s” is the current node value because all those values will be counted as pairs with s.

Here is when u will use BIT to find this value:

ans+=query(s+k)-query(s-k-1);

U find this in O(log n).Then update this current node’s value in BIT before going to its children.

By doing this u can find the answer for all vertices and hence for the whole subtree.

See my code for reference : https://www.codechef.com/viewsolution/13109792

Happy coding

try solving this

Okay I will try Thanks

Thanks although I don’t know BIT or segment trees yet. So, I’ll probably try this problem later.

Can you please elaborate your answer? What will you get in **ans** after performing this query? And why there is a need of update in this offline query?