Hello Codeforces!!↵
↵
In this blog, I want to present to you a beginner-friendly video lecture series on dynamic programming on trees/an editorial for the CSES tree algorithms section.↵
↵
[CSES](https://cses.fi/problemset/) is a brilliant problemset for people wanting to get started at competitive programming and get good at it.↵
↵
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.<br>[Link to the problems](https://cses.fi/problemset/)<br>↵
↵
Subordinates↵
------------↵
↵
Explanation : [https://youtu.be/fGznXJ-LTbI](https://youtu.be/fGznXJ-LTbI)<br>↵
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.<br>↵
Explanation : [https://youtu.be/RuNAYVTn9qM](https://youtu.be/RuNAYVTn9qM)<br>↵
AC code : https://github.com/kartik8800/CSES/blob/master/Tree%20Matching↵
↵
Tree Diameter↵
------------↵
↵
Explanation : [https://youtu.be/qNObsKl0GGY](https://youtu.be/qNObsKl0GGY)<br>↵
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.<br>↵
I feel Tree Distances II is easier compared to Tree Distances I and would recommend to try it first.↵
↵
↵
Explanation : [https://youtu.be/N7e4CTfimkU](https://youtu.be/N7e4CTfimkU)<br>↵
AC code : https://github.com/kartik8800/CSES/blob/master/Tree%20Distances%201↵
↵
Tree Distances II↵
------------↵
↵
This problem also uses the rerooting technique.<br>↵
Explanation : [https://youtu.be/nGhE4Ekmzbc](https://youtu.be/nGhE4Ekmzbc)<br>↵
AC code : https://github.com/kartik8800/CSES/blob/master/Tree%20Distances%202↵
↵
↵
Distance in Tree↵
------------↵
↵
This problem also uses the rerooting technique.<br>↵
Problem link: https://mirror.codeforces.com/contest/161/problem/D<br>↵
Explanation : [https://youtu.be/SOhZqL6HPjQ](https://youtu.be/SOhZqL6HPjQ)<br>↵
↵
↵
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](https://youtu.be/FAfSArGC8KY)<br>↵
↵
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](https://youtu.be/qPxS_rY0OJw)<br>↵
LCA slightly different from standard algorithm: [https://youtu.be/s9zZOVsF_eo](https://youtu.be/s9zZOVsF_eo)↵
↵
Distance Queries↵
------------↵
↵
Problem Statement : what is the distance between nodes a and b?<br>↵
Short explanation : Let LCA(a,b) be node x, what is distance between a and x?<br>Preprocess the levels of all the nodes in the tree. ↵
↵
lvl[i] : level of node i in the tree.<br>↵
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.<br>↵
Explanation: [https://youtu.be/i9ctLWyVSsA](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 :)↵
↵
<strong>UPD</strong>: added detailed explanation for binary lifting and video solution to Company Queries I.<br>↵
<strong>UPD</strong>: added detailed explanation for LCA techniques.↵
<br>↵
<strong>UPD</strong>: added solution to distance queries(CSES) and Distance in Tree(CF, VKCup,Problem D).↵
↵
In this blog, I want to present to you a beginner-friendly video lecture series on dynamic programming on trees/an editorial for the CSES tree algorithms section.↵
↵
[CSES](https://cses.fi/problemset/) is a brilliant problemset for people wanting to get started at competitive programming and get good at it.↵
↵
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.<br>[Link to the problems](https://cses.fi/problemset/)<br>↵
↵
Subordinates↵
------------↵
↵
Explanation : [https://youtu.be/fGznXJ-LTbI](https://youtu.be/fGznXJ-LTbI)<br>↵
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.<br>↵
Explanation : [https://youtu.be/RuNAYVTn9qM](https://youtu.be/RuNAYVTn9qM)<br>↵
AC code : https://github.com/kartik8800/CSES/blob/master/Tree%20Matching↵
↵
Tree Diameter↵
------------↵
↵
Explanation : [https://youtu.be/qNObsKl0GGY](https://youtu.be/qNObsKl0GGY)<br>↵
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.<br>↵
I feel Tree Distances II is easier compared to Tree Distances I and would recommend to try it first.↵
↵
↵
Explanation : [https://youtu.be/N7e4CTfimkU](https://youtu.be/N7e4CTfimkU)<br>↵
AC code : https://github.com/kartik8800/CSES/blob/master/Tree%20Distances%201↵
↵
Tree Distances II↵
------------↵
↵
This problem also uses the rerooting technique.<br>↵
Explanation : [https://youtu.be/nGhE4Ekmzbc](https://youtu.be/nGhE4Ekmzbc)<br>↵
AC code : https://github.com/kartik8800/CSES/blob/master/Tree%20Distances%202↵
↵
↵
Distance in Tree↵
------------↵
↵
This problem also uses the rerooting technique.<br>↵
Problem link: https://mirror.codeforces.com/contest/161/problem/D<br>↵
Explanation : [https://youtu.be/SOhZqL6HPjQ](https://youtu.be/SOhZqL6HPjQ)<br>↵
↵
↵
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](https://youtu.be/FAfSArGC8KY)<br>↵
↵
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](https://youtu.be/qPxS_rY0OJw)<br>↵
LCA slightly different from standard algorithm: [https://youtu.be/s9zZOVsF_eo](https://youtu.be/s9zZOVsF_eo)↵
↵
Distance Queries↵
------------↵
↵
Problem Statement : what is the distance between nodes a and b?<br>↵
Short explanation : Let LCA(a,b) be node x, what is distance between a and x?<br>Preprocess the levels of all the nodes in the tree. ↵
↵
lvl[i] : level of node i in the tree.<br>↵
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.<br>↵
Explanation: [https://youtu.be/i9ctLWyVSsA](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 :)↵
↵
<strong>UPD</strong>: added detailed explanation for binary lifting and video solution to Company Queries I.<br>↵
<strong>UPD</strong>: added detailed explanation for LCA techniques.
<strong>UPD</strong>: added solution to distance queries(CSES) and Distance in Tree(CF, VKCup,Problem D).↵
