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


DGCD - Editorial







Number theory, Segment Trees, Heavy Light Decomposition


You're given a tree of N vertices. Each vertex has a number written on it. Process two types of queries :

  1. Add d (input) to numbers of all vertices along the unique path between vertices u and v (both input)
  2. Find out GCD of all numbers on the vertices along unique path between vertices u and v (both input).


Use Heavy Light Decomposition of the tree to reduce problem to only linear paths. Use the fact that gcd(a, b, c, d..) = gcd(a, b-a, c-b, d-c...) to change segment updates to point updates.


It's a difficult problem and as with many other difficult problems as well - the secret of solving this problem is solving a simplification of the problem.

Simplification : Given tree is a linear path
So what can we do if given tree is a linear path? Now our change operations is reduced to to addition of a constant to a contiguous sub-array and our find opertion reduces to finding out gcd of all numbers on a contiguous sub-array. Experienced programmers would've seen immediately that a datastructure like segment tree with technique of lazy propogation could be useful for this problem, however what information is to be stored at each segment, that is not obvious. There are two very simple identities at the core of this problem. Assume (a,b) represents gcd(a,b).

  1. (a,b) = (a,b-a)
  2. (a,b,c) = (a,(b,c)) = ((a,b),c)

It is still not clear how these help us. Let us first try to see how gcd is changed (or rather how it is not changed) when we increment all the numbers of a sequence.

Say G = (A1,A2,...,An) and G' = (A1 + k, A2 + k, ... An + k)
Now using identities 1 and 2 we can say that : G is same as (A1, A2 - A1, A3 - A2..., An-An-1)
=> G = (A1, (A2-A1, A3-A2...., An- An-1))

So similarly G' = ( A1 + k, A2 + k - (A1 + k) , ...., An + k - (An-1 + k) )
=> G' = ( A1 + k, A2 - A1, A3 - A2, ..... An - An-1 )
=> G' = ( A1 + k, (A2-A1, A3-A2, ....., An - An-1 ))

Now call { A2-A1, A3-A2, ...., An - An-1 } as the difference sequence. So if we compare G and G', we see that much of the information has been retained through the gcd of the difference sequence. In particular it tells us what information we need to store at each segment of segment tree: first number of the sequence and the gcd of the difference sequence. With this information, its easy to find gcd of the segment : its the gcd of first number and gcd of difference sequence.

It's also easy to increment all numbers of the sequence by d, gcd of difference sequence remains unchanged and the first number increments by d. If we want to merge two consecutive smaller segments to make a larger segment, as we'd need to do with segment trees, we also need to store the last number of the segment.

Using this, it is easy to write a segment tree which can do all operations in O(logN) time, making it an O( (N + Q) * logN) solution.

Back to original problem:

We can solve original problem with the help of a technique called Heavy Light Decomposition of a tree. Essential idea is as follows. We divide the vertex set of the tree in O(N) linear chains such that following property holds : On the unique path between any two vertices u and v, there are utmost 2 * log(N) different chains. If we can find such a decomposition, we could build individual segment trees on each of these chains. Now a single query would correspond to quries on each of these O(log N) chains making a single query O( (log N)2) overall.

I'm not going to explain Heavy Light Decomposition here - rather I'd leave you with an exceptionally well written description of this technique. I myself learnt this technique from here.


Can be found here.


Can be found here.


QTREE on Spoj
QTREE3 on Spoj
IPSC 2009 problem L



This question is marked "community wiki".

asked 11 Jul '12, 16:33

yellow_agony's gravatar image

4★yellow_agony ♦♦
accept rate: 0%

edited 11 Jul '12, 16:56

admin's gravatar image

0★admin ♦♦

Tester's solution solves only a simplified version of the problem.


answered 11 Jul '12, 18:48

num314's gravatar image

accept rate: 0%


Thanks for pointing it out. Now the link has been fixed.

(12 Jul '12, 10:33) yellow_agony ♦♦4★

Want to add some information and to know other users ideas about C++ solution. I realized author's approach on the contest and get TLE, then i got rid of "vector <>"s and finally add static array and used it to allocate memory for segment trees for any path.


answered 12 Jul '12, 15:58

jughead's gravatar image

accept rate: 0%

Well it isn't necessary to dinamically allocate memory, since the total length is always the same, you could keep the sizes of each segment tree and keep everything in only one array. I did that, and it passed. For QTREE3 I also needed this optimization, guess it is always a good idea to do it this way.

(13 Jul '12, 07:12) MarioYC5★

I am getting TLE!! Can anyone HELP me ? my code :


answered 17 Feb '16, 22:19

deathstar's gravatar image

accept rate: 0%

edited 19 Feb '16, 00:51

what is the worst case that cause TLE?, i use HLD + segment tree + lazy update


answered 16 May '17, 16:47

whyzker's gravatar image

accept rate: 0%

Setters's solution gives WA.

Check this:


answered 05 Feb, 10:05

basilisk1995's gravatar image

accept rate: 0%

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: 11 Jul '12, 16:33

question was seen: 9,194 times

last updated: 05 Feb, 10:05