This 23.5 minutes video boils down to two lines: 1. If diameter goes through the root, it's given by 1 + largest height of a child of root + 1 + 2nd largest height of a child of root 2. If diameter doesn't go through the root, it's given by the largest diameter of a child of root. Take the max of 1 and 2. Return height and diameter from DFS function described above. Recurse. You're welcome.
Bro you are the best of the best DP teacher I have seen....Usually its very sleepy or boring tutorials of DP but yours is so interactive and to the point kinda thing... I just frickin Love it !. Please don't stop making videos bro..
Sir, i've been watching your videos for quite a few days now and i must say you're playlist of dp on trees and dp are very good. Please add some content on string manipulations as well.
Nice explanation! vector childrenDownPaths; can lead to O(NlogN) right? as you are sorting the vector. we can use max1 , max2 to restrict the complexity to O(N) .
Yes, The code Implemented by me has a worst case runtime of O(NlogN). And as you said it can easily be optimised to O(N) by doing some extra bookkeeping. I Implemented it like this so that the Implementation is easier for me and the code is more readable for the viewers :)
I'll try to upload an easier implementation when I get time and if it's possible. You could share your implementation too if it's easier I will upload that one :)
Guys, I am not able to understand how the ans in "diameter[src] = max(diameter[src], ans)" will every be maximum. Since which the else case in line 59 will push the maximum child which is "ans". So, if the maximum src is not included, but still the "ans" will never be maximum. Please, help me out.
see ans containes the diameter if we don't include the src node in the diameter , you are thinking that if we have included the maximum of downpath of all the child in the answer whereas sum of 2 maximum downpath of child +2 in line 59 case how will ans be greater than diamtere[src] but see care fully in case of ans its diameter of child not downpath. you can understand by this graph 7 1 2 2 3 3 4 5 6 2 5 6 7 see in this case ans will be greater in case of diameter[1].
cses.fi/paste/8aa862eb1e09e1aa112eeb/ Here is my solution using dfs. My solution seems to be more intuitive to me. Is there any more optimization I can do?
This 23.5 minutes video boils down to two lines:
1. If diameter goes through the root, it's given by 1 + largest height of a child of root + 1 + 2nd largest height of a child of root
2. If diameter doesn't go through the root, it's given by the largest diameter of a child of root.
Take the max of 1 and 2.
Return height and diameter from DFS function described above. Recurse. You're welcome.
Bro you are the best of the best DP teacher I have seen....Usually its very sleepy or boring tutorials of DP but yours is so interactive and to the point kinda thing... I just frickin Love it !. Please don't stop making videos bro..
Thanks man, glad to know you are enjoying the channel :)
Sir, i've been watching your videos for quite a few days now and i must say you're playlist of dp on trees and dp are very good. Please add some content on string manipulations as well.
I am currently planning a lot of topics, I will make sure I cover a lot of important and interesting topics on my channel :)
Aditya Verma Style :
#include
using namespace std;
vector tree[200001] ;
int ans = 0;
int solve(int src, int par) {
vector v ;
bool leaf = 1;
//Get 2 maximum depths of children (Hypothesis)
for(auto child : tree[src]) {
int t ;
if(child != par) {
leaf = 0 ;
t = solve(child, src) ;
v.push_back(t) ;
}
}
if(leaf) return 1 ;
sort(v.begin(), v.end()) ;
int mx1 = (v.size()-1 >= 0) ? v[v.size()-1] : 0 ;
int mx2 = (v.size()-2 >= 0) ? v[v.size()-2] : 0 ;
//A path that passes thru curr src root = 2 max depths summation
ans = max(ans, mx1 + mx2) ;
//Return the max depth to parent
return max(mx1, mx2) + 1;
}
int main() {
int n;
cin >> n ;
for(int i = 0 ; i < n - 1 ; i++) {
int a, b;
cin >> a >> b ;
tree[a].push_back(b) ;
tree[b].push_back(a) ;
}
solve(1, 0) ;
cout
I like this.
Bhaiya thanks for this amazing video after going through your lecture i atleast know how to approach a DP on tree problems.
Glad to know :)
You're welcome!
The best ever resource
Nice work bhaiya 👏👏. I was revising trees these days,now it will be easier for me because of your videos😊
Thankyou Siddhant and good luck with your revision :)
Nice explanation!
vector childrenDownPaths; can lead to O(NlogN) right? as you are sorting the vector.
we can use max1 , max2 to restrict the complexity to O(N) .
Yes, The code Implemented by me has a worst case runtime of O(NlogN).
And as you said it can easily be optimised to O(N) by doing some extra bookkeeping.
I Implemented it like this so that the Implementation is easier for me and the code is more readable for the viewers :)
Thanks for the explantion sir......Your videos are really helpful
Sir well explained sir can you pls make video on fenwick tree
Very well explained👍
Glad you liked it
same concept different implementation:
vvi adj;
int ans = 0;
int dfs(int node, int parents) {
int a1 = 0, a2 = 0;
for (auto child : adj[node]) {
if (child != parents) {
a1 = max(a1, dfs(child, node));
if (a2 < a1)
swap(a1, a2);
}
}
ans = max(ans, a1 + a2);
return a2 + 1;
}
this is giving wrong answer
best best best
i think you complicated this a little bit like you could have done this all inside one dfs func only but nice bit
I'll try to upload an easier implementation when I get time and if it's possible.
You could share your implementation too if it's easier I will upload that one :)
Guys, I am not able to understand how the ans in "diameter[src] = max(diameter[src], ans)" will every be maximum. Since which the else case in line 59 will push the maximum child which is "ans". So, if the maximum src is not included, but still the "ans" will never be maximum. Please, help me out.
see ans containes the diameter if we don't include the src node in the diameter , you are thinking that if we have included the maximum of downpath of all the child in the answer whereas sum of 2 maximum downpath of child +2 in line 59 case how will ans be greater than diamtere[src] but see care fully in case of ans its diameter of child not downpath.
you can understand by this graph
7
1 2
2 3
3 4
5 6
2 5
6 7
see in this case ans will be greater in case of diameter[1].
you made the explanation complex by using mathematical symbols and variables like c1,c2...ck , Haha, but nice
cses.fi/paste/8aa862eb1e09e1aa112eeb/
Here is my solution using dfs.
My solution seems to be more intuitive to me. Is there any more optimization I can do?
More cses problems