An alternative trick to solve many HLD problems using basic dfs

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

I use this post to try and explain an alternative to HLD that I have been using for more than a couple of months.

As many of you might be familiar HLD is a very tough thing to implement and is time-taking and must be implemented carefully.

Also if HLD sums are asked in short contests then it is going to be difficult to implement. Hence I came up with this technique.

I will try and explain this concept with the july long contest problem.

In this problem the value of number of nodes is given to be 10^5 which means maximum depth of the tree is 10^5 (worst case). What I do is I perform a dfs in the tree and for every node whose depth%1000=1, I store the values of all its ancestors.

In worst case the memory complexity is (1000+2000+...10^5)= 1000(1+2+3+....+100) = 5*10^6. After this I sort all these values and take a prefix xor.

Now for each query I have to travel up atmost 1000 ancestors and arrive at an ancestor whose depth%1000=1 and from there we can find xor of all elements less than k. We do this for both nodes U and V(source and destination). Because of the property of XOR all the values of the ancestors are canceled out.

Hence each query is (1000*Q) in the worst case.

Though this is somewhat testing the upper limits we can actually dynamically change the value in which we store the ancestors(1000 in this case). However this has not been required so far for me.

This is because we such situations(which test upper limits) rarely occur but even for that depending on the tree we can change the depth value.

Another question I solved using this techique is GPD in codechef. GPD can also be solved using persistent trie but this method is far more easier.

My solutions for : PSHTTR : GPD

In case for sum of values in the path between 2 nodes we can store sum of ancestors and we can find answer by:

sum upto U + sum upto V — sum upto LCA(U,V)

Upd1: If the maximum depth of tree is less than 1000 you can directly climb up the tree and do the calculations.

Also as Diversity pointed out there can be cases where there are 10^5-1000 nodes which have depth%1000=1. For overcoming this we can have an initial dfs that has a count of depth%1000=1,2,3,4,...,999 and we can choose values which satisfy the memory limit using count(This is the dynamic change of value I mentioned).Also I believe we can strech upto depth%2000.

Note: I have not tried implementing this technique of changing node depth of storing values dynamically.