Queries on Tree : Course (CodeNCode) (8 Aug 2020 : 2 new centroid decomposition lecture added)

tutorial
, ,
1

Hello Codechef community.
I am currently working on a course focusing on techniques which are use to answer queries which are asked on trees like Mo's algorithm on trees , HLD , merge smaller into bigger and so on.


Here is the list of lectures made till now

L00 : Course Overview

L01 : Euler Tree Technique / Tree Flattening

L02 : Tree & Queries | Codeforces | Rated 2400 (Explaining Mo’s on tree)

L03 : Tree & Queries Part 2| Codeforces | Rated 2400 (Explaining Mo’s on tree)

L04 : Path Queries & Mo’s Algorithm

L05 : GOT (SPOJ) : Application of Mo’s algorithm on path query

L06 : Introduction to Centroid Decomposition & Related Problems

L07 : Height and Structure of Centroid Decomposition

L08 : Building Centroid Decomposition Tree (C++ Implementation)

More lectures will be added soon
any suggestion is welcome.
Tank you for your precious time.
CodeNCode

48 Likes
2

Thanks brother…you are doing amazing work for CP community, best wishes to you :slight_smile:

1 Like
3

you’re welcome man

3 Likes
4

Lecture 2 Doubt:

In your code in the comparator function why the parity of the block is considered for sorting ?

5

this is one of the optimizations of Mo’s algorithm
you can read more about optimizations on Mo’s here.

6

2 May 2020 : 1 video added
L04 : Path Queries & Mo’s Algorithm

1 Like
7

What about dynamic programming course

8

I will add more videos in Dynamic Programming Playlist as well soon.

9

5 May 2020 : 1 video added
L05 : GOT (SPOJ) : Application of Mo’s algorithm on path query

10

This question also uses Tree Flattening technique. Can you explain this using segment tree or sqrt decomposition?
Thanks for your help!

11

Thanks for suggestion , I will surely look into this.

2 Likes
12

In L05, you use for 2nd type of queries dist=tout[a] to tin[b] +lca
can we use like this
dist=start[lca] to tin[a] + tout[b] to end[lca]
?
And thanks for such a great explanation

13

I think we can do this , but then a single path query will be transformed into 2 queries in Mo’s

  1. start[lca] to tin[a]
  2. tout[b] to end[lca]
14

big shout out to you bro to put your so much efforts for us…

15

thanks brother.
just playing my part in the growth of CP community.

16

i will surely reduce complexity i guess

17

I would request you to kindly make videos on atcoder dp contest. They are really very good and involves dp on graphs and tree including convex hull optimization. Do check it

18

I am little busy with Number theory and this series.
I will try to make videos on them too.
Thanks for suggestion btw

19

hi you are doing good work

20

hello , and thanks for the complement