You are not logged in. Please login at to post your questions!


Abacus'17-OLPC Geek Tree Solution

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

link -

asked 18 Mar '17, 00:01

mathecodician's gravatar image

accept rate: 7%


answered 18 Mar '17, 01:59

aminuteman's gravatar image

accept rate: 13%

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:


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 :

Happy coding ;)


answered 18 Mar '17, 00:50

aloochaat1998's gravatar image

accept rate: 16%

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

(18 Mar '17, 01:06) mathecodician6★

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?

(18 Mar '17, 01:38) bansal12325★

Can someone tell the solution for this problem too :


answered 18 Mar '17, 00:11

tihorsharma123's gravatar image

accept rate: 15%


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.


answered 18 Mar '17, 00:21

mathecodician's gravatar image

accept rate: 7%

Okay I will try Thanks :)

(18 Mar '17, 00:27) tihorsharma1232★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 18 Mar '17, 00:01

question was seen: 367 times

last updated: 18 Mar '17, 01:59