Dynamic Programming on Tree(Complete Series)

Hi Everyone

In this blog, I want to present to you a beginner-friendly video lecture series on dynamic programming on trees.

My aim till now has been to make the explanations intuitive, crisp and clear. I feel even a beginner will be able to benefit from these video lectures.

So let’s get started.
Link to the problems

Subordinates

Explanation : https://youtu.be/fGznXJ-LTbI

AC code : https://github.com/kartik8800/CSES/blob/master/Subordinates

Tree Matching

Somehow I feel some other nice approaches are also possible, please do share.

Explanation : https://youtu.be/RuNAYVTn9qM

AC code : https://github.com/kartik8800/CSES/blob/master/Tree%20Matching

Tree Diameter

Explanation : https://youtu.be/qNObsKl0GGY

AC code : https://github.com/kartik8800/CSES/blob/master/Tree%20Diameter

Tree Distances I

This problem uses the rerooting technique, we evaluate the answer for every node assuming it to be the root of the tree. If we do this naively this will be O(N^2) time but if we do this using something known as the reroorting technique and propogate partial answers of parent node with respect to the child nodes we can optimize our solution to O(N) overall time complexity.

I feel Tree Distances II is easier compared to Tree Distances I and would recommend to try it first.

Explanation : https://youtu.be/N7e4CTfimkU

AC code : https://github.com/kartik8800/CSES/blob/master/Tree%20Distances%201

Tree Distances II

This problem also uses the rerooting technique.

Explanation : https://youtu.be/nGhE4Ekmzbc

AC code : https://github.com/kartik8800/CSES/blob/master/Tree%20Distances%202

Distance in Tree

This problem also uses the rerooting technique.

Problem link: https://codeforces.com/contest/161/problem/D

Explanation : https://youtu.be/SOhZqL6HPjQ

Company Queries I

This problem uses a technique(the technique itself uses DP) known as Binary lifting. I will be adding a detailed lecture on binary lifting with code.

Explanation : https://youtu.be/FAfSArGC8KY

Company Queries II

This problems requires us to know a technique to calculate LCA of two nodes in a tree in O(logN) time. Evaluation of LCA in O(logN) can be done using binary lifting. I will add a more detailed video soon.

LCA using binary Search: https://youtu.be/qPxS_rY0OJw

LCA slightly different from standard algorithm: https://youtu.be/s9zZOVsF_eo

Distance Queries

Problem Statement : what is the distance between nodes a and b?

Short explanation : Let LCA(a,b) be node x, what is distance between a and x?
Preprocess the levels of all the nodes in the tree.

lvl[i] : level of node i in the tree.

Ans to query distance(a,b) = (lvl[a] — lvl[x]) + (lvl[b] — lvl[x]) where x is the LCA(a,x).

Again finding LCA of two nodes can be done in O(logN) time and levels of all nodes can be found in O(N) time preprocessing.

Explanation: https://youtu.be/i9ctLWyVSsA

Will try to add the remaining problems also as soon as possible for me.

I am also planning to add video lecture series on more topics which might be helpful to beginners as well intermediates. I will be open to feedback and suggestions.

I hope people find this helpful :slight_smile:

16 Likes

that’s great bro. Thank you so much.

1 Like

Nice initiative!

1 Like

happy to know you found this helpful :slight_smile:

Thanks Palak!

I have added the following tutorials.

P1 : https://youtu.be/fGznXJ-LTbI (Easy)
P2 : https://youtu.be/RuNAYVTn9qM (Medium)
P3: https://youtu.be/qNObsKl0GGY (Easy-Medium)
P4: https://youtu.be/N7e4CTfimkU (Medium)
P5: https://youtu.be/nGhE4Ekmzbc ( Medium)
P6: https://youtu.be/FAfSArGC8KY (Easy-Medium)

All problems use DP on Trees.
P1 is a great problem for beginners to get started with DP on Trees
P2 is a really interesting problem.
P3 is generally asked in coding interviews.
P4 and P5 use the DP on tree with rerooting technique(explained in video).
P6 in my opinion is the best problem to learn about binary lifting.

I have provided a crisp and clear explanation of the technique of binary lifting and then solved P6 and explained the coding part also.

3 Likes

I think you should post it on codeforces for more reach!!

2 Likes

Thanks for the suggestion, I will do that too once I have completed a few more problems.

Would you mind checking out a video or two?

I’d happy to get some suggestions for improving further videos.

I hope you’ll find the content helpful.

2 Likes

Cool it can also be uploaded as solution of cses tree section which will interest more people to watch :slight_smile:

1 Like

Sure thanks for the suggestion.
https://codeforces.com/blog/entry/79857

Added crisp and clear, beginner friendly explanation to binary lifting with code: https://youtu.be/FAfSArGC8KY

1 Like

UPD: added more problems