### kartik8800's blog

By kartik8800, history, 7 months ago,

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 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.

## 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 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.

## 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.
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

## Appleman and tree

problem statement: https://codeforces.com/problemset/problem/461/B
solution video: https://youtu.be/gj0zp--fBL8

## Binary Tree Cameras Leetcode

problem statement: https://leetcode.com/problems/binary-tree-cameras/

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 :)

UPD: added detailed explanation for binary lifting and video solution to Company Queries I.
UPD: added detailed explanation for LCA techniques.
UPD: added solution to distance queries(CSES) and Distance in Tree(CF, VKCup,Problem D).
UPD: added solution to appleman and tree from codeforces.
UPD: added solution to binary tree cameras from leetcode.

• +117

 » 7 months ago, # |   +5 Very usefull!! Thanks!
 » 7 months ago, # |   +5 Nice I was looking for some tutorials and I found this!!
 » 7 months ago, # |   0 Auto comment: topic has been updated by kartik8800 (previous revision, new revision, compare).
 » 7 months ago, # |   +5 Your Range Queries CSES Editorials, now these. You are surely doing a great help to all of us. Thanks a lot :)
•  » » 7 months ago, # ^ |   0 Thankyou for the positive words :) I'm also making a series on dynamic programming on my channel, do check that out too.
•  » » » 7 months ago, # ^ | ← Rev. 2 →   +5 surely your content will help many just keep uploading content .Channel will surely grow with time once it has a quality content.
•  » » » 4 months ago, # ^ |   +5 Kartik Bro(I am your friend from Telegram, I praised your handwriting :) )Here is my editorial series for Graph Series: https://codeforces.com/blog/entry/82746#comment-697257
 » 7 months ago, # |   +9 Tree Distances I can be solved without rerooting. The idea is to calculate the two longest paths that go only downward from each node, and then to start another dp to consider also the paths that go upward, being careful not to choose the same node twice on the same path. Submission
•  » » 7 months ago, # ^ |   0 Thankyou for sharing. It would be great if you could elaborate a little more on: start another dp to consider also the paths that go upward I have trouble understanding what exactly will this dp state represent?
•  » » » 7 months ago, # ^ | ← Rev. 2 →   +5 CP Handbook, p. 137
•  » » » » 7 months ago, # ^ |   0 got it, thankyou.
 » 7 months ago, # | ← Rev. 2 →   +7 Checkout thumbnail for my new video on Binary lifting.PS: will upload by tonight.UPD : check it out here: https://youtu.be/FAfSArGC8KY
 » 7 months ago, # | ← Rev. 2 →   0 for Tree Distances II, a good article , https://leetcode.com/articles/sum-of-distances-in-tree/
•  » » 7 months ago, # ^ |   0 looks somewhat like the reroorting technique only, not sure though didn't read it thoroughly. My video solution is similar to this I guess.
•  » » » 7 months ago, # ^ |   0 Yah it is similar, I saw it after commenting.
 » 7 months ago, # |   +1 All hail _LeMur_ the God of DP on trees.
•  » » 7 months ago, # ^ |   +8 orz
 » 7 months ago, # |   0 Auto comment: topic has been updated by kartik8800 (previous revision, new revision, compare).
 » 7 months ago, # |   +5 Is tree distance 1 can be solved like this — find the maximum of (distance between node and diameter end point1,distance between node and diameter end point2).
•  » » 7 months ago, # ^ |   0 Yes it looks alright to me.nice Algorithm. I think the proof will be similar to tree diameter BFS approach proof.Did you try and Implement your idea?
•  » » » 7 months ago, # ^ |   +5 Yes, it's working but I prefer rerooting technique as rerooting is used in many questions.
•  » » » » 7 months ago, # ^ |   +1 Hi5, same here. I try to avoid Algorithms which I cannot prove mathematically.still i did like your approach:)
•  » » » » » 7 months ago, # ^ |   0 Thanks.
 » 7 months ago, # | ← Rev. 2 →   +1 Interested people may also checkout detailed video explanations for the DP section of CSES.Introduction to Dynamic Programming
 » 7 months ago, # |   +5 Carry on brother!!
 » 6 months ago, # |   0 I think "tree distances I" can be solved in an easier way by using the diameter of the tree. I guess the maximum distance for each node is max of distance between the node and the two ends of diameter. This passed for me.
•  » » 6 months ago, # ^ |   +3 Yes we have discussed this approach here: https://codeforces.com/blog/entry/79857?#comment-658637
 » 6 months ago, # |   0 Auto comment: topic has been updated by kartik8800 (previous revision, new revision, compare).
 » 6 months ago, # |   0 Auto comment: topic has been updated by kartik8800 (previous revision, new revision, compare).
 » 5 months ago, # |   0 It was a great series man! Thank you so much . Can any one help me with this dp on trees Problem ?
 » 7 weeks ago, # |   0 Auto comment: topic has been updated by kartik8800 (previous revision, new revision, compare).
 » 7 weeks ago, # |   0 Here is a another clean approach for Tree Distances II which I also like that! #include #include #include #include #include #include #include #include #include #include #include #define LL long long #define FOR(i, a, b) for (int i = a; i < b; ++i) #define REP(i, a, b) for (int i = a; i <= b; ++i) #define X first #define Y second #define pb(a) push_back(a); #define pii pair #define pLi pair #define piL pair #define pLL pair #define ar array using namespace std; const int mxn = 2e5 + 5; LL dp[mxn], node[mxn], n; vector a[mxn]; void dfs (int p, int u) { for (int v : a[u]) if (v != p) { dfs(u, v); dp[u] += node[v] + dp[v]; node[u] += node[v]; } ++node[u]; } void dfs2 (int p, int u) { dp[u] += (dp[p] - dp[u] - node[u]) + n - node[u]; for (int v : a[u]) if (v != p) dfs2(u, v); } int main() { //freopen("D:\\test.txt", "r", stdin); //freopen("D:\\test2.txt", "w", stdout); cin >> n; REP(i, 2, n) { int u, v; cin >> u >> v; a[u].pb(v); a[v].pb(u); } dfs(0, 1); for (int v : a[1]) dfs2(1, v); REP(i, 1, n) cout << dp[i] << ' '; } 
 » 7 weeks ago, # |   0 Auto comment: topic has been updated by kartik8800 (previous revision, new revision, compare).