DP on Trees: Tree Distances I
Вставка
- Опубліковано 29 січ 2025
- Beginner friendly and clear explanation to the problem cses.fi/proble...
I recommend trying on your own before you watch the video :)
Github llink for code: github.com/kar...
My Codechef profile : www.codechef.c...
My Codeforces profile : codeforces.com...
If you found this helpful, like share and subscribe!
Super useful books for algo ds and programming fundamentals!
1. Introduction to Algorithms by Cormen: amzn.to/35AmQqu
2. The Algorithm Design Manual: amzn.to/2K9RGPq
3. Fundamentals of Data Structures in C++: amzn.to/2LCwIsN
4. Object-Oriented Programming by E Balagurusamy: amzn.to/2Xxmdtr
5. Head First Java: amzn.to/39kb44K
6. Cracking the coding interview: amzn.to/3iDOHLK
7. Database System concepts: amzn.to/3pisuFQ
8. Operating Systems: amzn.to/39fcmis
9. Discrete Mathematics: amzn.to/2MlgCE6
10. Compiler Design: amzn.to/3pkYvx2
I solved it simply by finding the two endpoints(farthest nodes) and then apply BFS on these two and find the distance from endpoint to other nodes, then our answer is simply max(endpoint1[i],endpoint2[i])
do you have any proof for this solution ?
Oh yeah this is also a brilliant method!
@@BantiKumar-gd3lr The proof is same as for why only 2 dfs is required to find the diameter of a tree. Check CodeNCode's video if you aren't able to prove it yourself. Cheers mate
Nice
@@arjunj2125, I tried this approach and got the wrong answer
what happened is the two farthest nodes lie on the same path from the root, so I was getting the wrong answer.
Can you tell how to implement this approach
Oh good!! What an explanation.
Superb man, I mean the question was too difficult and you made it look easy.
Glad you liked it
Can you explain why the initial call to the solve function have partial answer as -1???
Awesome Explanation sirji! Please keep adding such videos!
Is the choice for node g limited to leaf nodes? because it's partial solution will be 1 and that can be propagated to its adjacent nodes. Partial ans(g/p) will not have to be computed for a leaf node, but for any internal node this wouldn't necessarily be 1.
is it a Re-Rooting technique ?
Yes
How to propagate the answer downwards in the tree?
is this the same as in out dp?
Hi kartik bahi , orz
I find difficulty while implementing the solution to medium level problems. How should i strategize so that can imporove that part.
Hey Kartik what is the difference between this and the diameter? There also we were finding diameter of every node same as here?
i have this approach like first find the two farthest nodes in the tree let's denote them by A and B. and let's run BFS from both of this and let minimum distance from A for all nodes in the tree be stored in distA and same for B in distB. now for any node if we want to calculate the answer for let's say C. now if you observe very carefully and keep considering the fact that the diameter is from A to B and its length is constaant. only then you will realise that for C answer will be max(distA[C], distB[C]).
I am pretty sure that what I have said makes sense. Can you confirm this sir? i am too lazy to implement this.
I think it's correct, check my DP ON TREES blog on CF there was a similar discussion there i guess.
Nice explanation!
I also wanted to know what approach do you take in a situation where you cannot pass certain test cases? Do you dry run the code or are there other parameters as well that you keep in mind?
Hi Atishay, normally I would recommend proving your algorithms. If you are able to prove it mathematically then there is no scope left for any testcase to fail. However this is not always practical when we are low on time(coding tests etc) so then I would try coming up with small testcases for which I know the correct answer and see the output produced by my code.
I suggest you to always try to prove your algorithms when you are practicing this will certainly help you to improve :)
@@AlgosWithKartik Like how do you prove this exactly?
Could you explain ans [src] = line in the end ?
Nice Question
Very Nice Explanation ! Really made the question look simple
Thanks Parth
Amazing explaination sir.
Nice explanation sir....thanks a lot for such a useful content
I was able to think of the same solution what you discussed but I am facing difficulty in implementation can you suggest me some tips how can I improve I try to implement by myself but in the end, I have to watch your solution
Practice practice and practice!
Try writing modular codes.
Why don't we use directed edges only? So that the extra check src != par get resolved?
I had done that but it's saying wrong answer can anyone tell why?
trees are never directed
simpler solution and explanation exists.
using prefix and suffix just overcomplicates things.
Yes a simpler solution exists but I find it much harder to prove it's correctness.
The primary goal for this playlist is to learn how DP can be applied to Tree-like structures which couldn't be learned through the simpler solution.
Well explained. Thank you.
Glad you liked it!
Best solution
Thanks a lot.It was very helpful.
Happy to know you liked it.
Do share it with your friends too :)
Nice explanation 👌👍
Thanks Sagar!
very well explained sir !
Thanks Ovi :)
there is a mistake while writing, it should be 1 + partial_ans(grandparent/parent), it is however correct in code.
if you solve the question using bfs, it's way easier than this. this is unnecessary overkill.
please share your solution, thanks!
tell prove for that
I could only think BFS and evaluate depth.... Prefix max sum was really good
To be honest, these questions are easy to understand but implementation is tricky and u r not doing that. (Though it's best content)
Realest comment
I think, this is so called In-Out Dp technique.
I think it's called the rerooting technique.
@@AlgosWithKartik yeah you are right ,
blogarithms.github.io/articles/2019-10/inout-dp-tree
I learn from this blog,so that i know this in that name.
@@MarufHasan-cg6tq what's in the name anyway :p
partial ans topic unclear
should have avoid complex coding . See the comments people have done it easier way.
You should make a proper plan before making any video. Without any preparation, you're just going nowhere and you even don't know that to make it simple you are making it more complex for your audience to understand.
So, before creating any video at least think a few minutes and divide the lesson into a few steps. Right down the steps on a notebook. Then try to make the video following those steps. This will make your work more easy and also easier for your audience to understand the lesson.
Sirf mujhe hi code smjh nhi aaya ya kisi aur ko bhi (ب_ب)thoda clear samjhaya karo bhaiya confuse hogya end me
this is how i did it
vectortree[200001];
void dfs(int source,int par,vector&dist){
for(auto it:tree[source]){
if(it!=par){
dist[it]=1+dist[source];
dfs(it,source,dist);
}
}
}
void solve() {
ll n;
cin >> n;
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
tree[x].push_back(y);
tree[y].push_back(x);
}
vectordist(n+1,0);
//did dfs from the 1 to find the longest node from the 1
dist[1]=0;
dfs(1,0,dist);
ll maxi=0;
int z=1;
for(int i=1;imaxi){
maxi=dist[i];
z=i;
}
}
//did dfs from the longest node to find the other endpoint
vectordist2(n+1,0);
dfs(z,0,dist2);
maxi=0;
int z1=1;
for(int i=1;imaxi){
maxi=dist2[i];
z1=i;
}
}
vectordist3(n+1,0);
dfs(z1,0,dist3);
for(int i=1;i
Thanks a lot.It was very helpful.
Thanks a lot.It was very helpful.