DP on Trees: Tree Matching
Вставка
- Опубліковано 6 лют 2025
- Beginner friendly and clear explanation to the problem cses.fi/proble...
I recommend trying on your own before you watch the video :)
Github link for code: github.com/kar...
Code contributed by Prashant Kumar : ideone.com/AkuUN5
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 am having such a great time watching your videos whenever I am getting stuck in the CSES Problem Set. I just love how nicely you reduce so many problems to simple DP problems. Great work man.
Thanks a lot Priyansh :)
Although it won't affect the time complexity but we don't need to compute prefix and suffix vectors.
we can use dp[src][0] while calculating dp[src][1]. just subtract the contribution of current child in dp[src][0].
Amazing Explanation !!
I think that should work, thanks for sharing.
Do share your implementation too when you get time for that.
@@PrashantKumar-bn7ls Thanks for sharing, I'll add your code in description too :)
@@AlgosWithKartik alright :)
@@PrashantKumar-bn7ls great to see, how you take care of prefix and suffix sums Thanks for sharing your code :)
@@PrashantKumar-bn7ls can you please explain
dp[src][1]=MAX2(dp[src][1],1+ dp[child][0]+( dp[src][0]-MAX2(dp[child][0],dp[child][1])));
Thanks Kartik 😅i misunderstood the problem statement. You made it Clear.
my cpp solution : -
1. make a tree in the form of adjacency list
2. make a dfs call to any node considering it to be root ( in did for '1')
3 . In a dfs call we need to get the max possible pairs from the subtree
So we are considering all the possibilities and will take the max value out of these for the current node and will store it. So we don't need to calculate it again and again.
-- a. don't take the current node and sum all the pairs possible from the all child subtrees.
-- b. take the current node and a each child node iteratively, so if we are pairing the current node with one of its child node, the subtrees of that child node are also added and take rest of the pairs from all other child subtrees as it is.
#include
using namespace std;
const int M = 1e9 + 7;
vector tree;
vector dp;
int dfs(int v, int p)
{
if (dp[v] != -1)
return dp[v];
int total = 0;
for (auto c : tree[v])
{
if (c != p)
total += dfs(c, v);
}
int ans = total;
for (auto c : tree[v])
{
if (c != p)
{
int ansChild = 0;
for (auto c1 : tree[c])
{
if (c1 != v)
ansChild += dfs(c1, v);
}
ans = max(ans, 1 + total + -dp[c] + ansChild);
}
}
return dp[v] = ans;
}
int main()
{
int n;
cin >> n;
tree.resize(n + 1);
dp.resize(n + 1, -1);
for (int i = 1; i < n; i++)
{
int a, b;
cin >> a >> b;
tree[a].push_back(b);
tree[b].push_back(a);
}
auto ans = dfs(1, -1);
cout
ans = max(ans, 1 + total + -dp[c] + ansChild); did not understood this line
Actually no need to maintain prefix and suffix sums, we can use a simple trick instead.
void dfs(int cur,int par) {
for(int nbr : tr[cur]) {
if(nbr != par) {
dfs(nbr,cur);
dp[cur][0] += max(dp[nbr][0],dp[nbr][1]);
}
}
for(int nbr : tr[cur]) {
if(nbr != par) {
dp[cur][1] = max(dp[cur][1] ,dp[cur][0] - max(dp[nbr][1],dp[nbr][0]) + dp[nbr][0] + 1);
}
}
}
Hey,I thought of the same thing,but messed up in the implementation.Can you help me figure out my mistake?This is my code:#include
#define pb push_back
using namespace std;
int helper(int node,vector&adj,int parent,vector&dp,bool take){
if(dp[node][take]!=-1)return dp[node][take];
int ans = 0;
for(int adjNode:adj[node]){
if(adjNode == parent)continue;
if(!take){
ans += max(helper(adjNode,adj,node,dp,take),helper(adjNode,adj,node,dp,!take));
}
else{
ans = max(ans,helper(node,adj,parent,dp,!take) - max(helper(adjNode,adj,node,dp,take),helper(adjNode,adj,node,dp,!take))
+ helper(adjNode,adj,node,dp,!take));
}
}
if(take)ans++;
dp[node][take] = ans;
return dp[node][take];
}
int main()
{
int n;
cin>>n;
std::vectoradj(n);
for(int i = 0;i>a>>b;
adj[a-1].pb(b-1);
adj[b-1].pb(a-1);
}
vectordp(n,vector(2,-1));
cout
@@mayanknichlani no
even one for loop is sufficient , lol 😂😂😊😊
void dfs(int node,int par,vectoradj[]){
dp[node][1] = INT_MIN;
for(auto it:adj[node]){
if(it!=par){
dfs(it,node,adj);
dp[node][0]+=max(dp[it][0],dp[it][1]);
dp[node][1]= max(dp[node][1],min(0,dp[it][0]-dp[it][1]));
}
}
dp[node][1]+= ( dp[node][0] + 1);
}
superb explanation , we want our old Kartik sir back who used to make videos on cses tree and graph problems
thanks for such an amazing explanation , this problem is crystal clear to me now, and your approach is really great. please keep making these videos.
I solved it by simply traversing the tree using dfs
1. maintained a set
2. preform dfs
3. during dfs check if both the node and the parent is in the set or not
4. if not present ,, push node and parent into the set
5. print size(set)/2
thanks , it's much more simplier
Damn, bro you nailed it !!
Bro it's simple but it is n square solution
will give wrong answer as we cont judge which child parent combo to take out of all the childs the parent has
It will fail for this scenario.
1
4
1 2
1 3
2 4
The expected output is 2 but your code output is 1.
I just paused your video and think about it and then thought ki diameter nikalu or ceil(diameter/2) kru to answer mil jayega. I implemented that and got 7 correct out of 13 and then watched your video, thanks really nice explanation :)
Keep going and thanks for the positive words :)
I was thinking of solving this problem greedily by picking up an edge such that it contains a leaf as its endpoint and then remove all the edges that are connected to the other endpoint (non-leaf). This way new leaves will be generated every time some edges are removed or picked. I was wondering why this would fail. If you have a sample test case for this or maybe you can let me why this seems to wrong. Would be waiting for your response.
Actually, it worked out by this method. The idea was to greedily pick up edges such that one of the endpoints is a leaf. Here is the link to my code:ideone.com/cBimZw
Did you try proving it?
@@AlgosWithKartik I think whenever I solve a problem greedily I hardly prove it .... I just rely on my intuition and then just wait for the verdict to know whether I was thinking the right thing or not. What do you suggest should I always prove it before submitting it? I don't even know how to prove this one lol.
@@PriyanshAgarwal actually it is impractical to always prove your solution when you are in a short contest but while practicing I would highly suggest that we should try to prove the algorithm.
Imagine being in a coding interview and giving this solution when the interviewer was only aware of a DP solution. You will need to at least provide a convincing proof if not a formal rigorous proof otherwise I don't think the interviewer will be impressed.
@@PriyanshAgarwal and above all this, I feel the attempt to prove algorithms actually helps us become a better problem solver in general.
what an explanation sir !! , learned new something if dp on trees than u can make state where dp(u) will be like anything related to that subtree. Thanks A Lot
Your explanations are great! Have you considered giving a tutorial on RMQ, Sparse tables, etc? I'd really appreciate it.
Yes I was already considering making videos on sparse table, sqrt root decomposition and more.
Sir your explanations are really good........you are making the life of lot of students easy.Please continue this work....
Thanks a lot........
your explainations are so cool sir. i have been able to solve so many dp problems by myself. thank you sir for your contribution to the cp community.
Thankyou
best tutorials on dfs+dp on tree
Kartik the videos are really great man....do update this playlist with the rest of the cses tree algorithms problems...and also if possible add solutions for the graph theory set as well...like ur videos been a genuine help to me man
I am really happy to know that man :)
Do support by sharing the channel with your class.
Thnx a lot for ur contribution ...Really helped
Just a dbt that why u considered leaf separately ? means any reason ?
how u decided , this is not greedy??
elegant❤️
is this same as HOUSE ROBBER 3 problem from leetcode ?
Just saw the title of the video as Dp on Trees. Then went to solve the problem again,took time,and finally solved it with accepted solution😄
Very well explained! Thanks!
Thanks for the good explanation
Brother,
after understanding question ,With in 10Min I got Idea that I should use DP and Prefix Sum to solve this problem.
I have this approach in mind.
I have confidence that I can solve.But I m getting afried of coding it.
I know this msg dosent sense but I m saying my inner feeling
I understand your condition and only solution to this is to practice coding.
You'll get good!
please make videos on Additional Problems of cses
great explanation 🔥🔥 !! Thanks
#include
using namespace std;
void dfs(int curr, int par, map &mp, vector &adj, vector &edges)
{
// main code
for (auto x : adj[curr])
{
if (x != par)
{
// first ask to compute it;s set results
dfs(x, curr, mp, adj, edges);
/// now if nbr already in the set : no need to add this
//nbr not present that means now i can add an edge with it if i am also not in the set
if (mp.find(x) == mp.end())
{
if (mp.find(curr) == mp.end())
{
mp.insert({x, 1});
mp.insert({curr, 1});
edges.push_back({curr, x});
}
}
}
}
}
int main()
{
int n;
cin >> n;
vector adj(n + 1);
map mp;
for (int i = 0; i < n - 1; i++)
{
int x, y;
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
vector edgs;
dfs(1, -1, mp, adj, edgs);
cout
Kartik Sir you are doing a great job. Sir we need some interview prep questions too :)
Surely Vivek, my goals for the channel include CP, coding Interviews and University level algo DS videos. I wish to cover non-trivial problems and provable solutions to those problems.
It might take some time for everything to happen but It will as long as people keep Enjoying the content and joining the channel :)
For now you will enjoy the DP series which is helpful for product based companies :)
I always had issues with DP on trees problems, now I can fully grasp how to structure these kind of problems thanks.
please upload more problems on dp
Thanx man :)
Vaiya can we use LCA for every node and use hashset and add all the LCA into hashset and at last print the size of hashset for this problem?
I didn't get what you meant by "LCA for every node"
@@AlgosWithKartik yes vaiya I was wrong .
Loved it!
Nice explanation bro
why prefixes and suffixes.. just use dp[node][0] as total sum and subtract the answer for only child we are calculating dp[node][1]
i think we don't need prefix and suffix array, should have stored sum of all answers of all the child sub-trees
//A relatively simpler version without prefix and suffix sums
#include
#include
#include
using namespace std;
void dfs(int curr, int par, vector* adjlist, vector& dp){
for(auto x : adjlist[curr]){
if(x!=par){
dfs(x, curr, adjlist, dp);
dp[curr][0]+=max(dp[x][0], dp[x][1]);
}
}
for(auto x : adjlist[curr]){
if(x!=par){
dp[curr][1]=max(dp[curr][1], (1+dp[curr][0]-(max(dp[x][0], dp[x][1])-dp[x][0])));
}
}
}
int main() {
int n;
cin>>n;
vector adjlist[n];
for(int i =0; i>u>>v;
u--;v--;
adjlist[u].push_back(v);
adjlist[v].push_back(u);
}
vector dp(n, vector(2, 0));
dfs(0, 0, adjlist, dp);
cout
🙌🙌🙌
Thanks for ur video. I have a solution (python) like this:
def dfs(u, p):
global dp0, dp1
for v in adj.get(u, []):
if v == p:
continue
dfs(v, u)
dp1[u] = max(dp1[u], 1 + dp0[v] + (dp0[u] - max(dp0[v], dp1[v])))
dp0[u] += max(dp0[v], dp1[v])
Does this make sense?
looks good, try submitting it on the cses platform.
Kartik Arora will do, many thanks bud!
@@AlgosWithKartik the above solution failed, but this worked, not know what happened:
void dfs(int u=0, int p=-1) {
for (int v: adj[u]) {
if (v == p) continue;
dfs(v, u);
// dp1[u] = max(dp1[u] + max(dp0[v], dp1[v]), 1 + dp0[v] + dp0[u]);
// dp0[u] += max(dp0[v], dp1[v]);
dp0[u] = max(dp0[u] + max(dp1[v], dp0[v]), 1 + dp1[v] + dp1[u]);
dp1[u] += max(dp1[v], dp0[v]);
}
}
Kartik Bro please do recursive + memorization . These Dp table is really hard to learn ..
Great work ! Very well explained ....... ! :- )
Thanks..!
The number of views and like are low, because the board is small, and to a beginner, its like out of sight out of mind.
Cool
I thing my solution is much more simpler
void dfs(int s,int p){
if(adj[s].size()==1 && s!=1){
val[s]= true;
return;
}
bool v= false;
for(int u:adj[s]){
if(u==p) continue;
dfs(u,s);
v = v || val[u];
}
if(v){
res++;
val[s]= false;
return;
}
val[s]=true;
}
scan the tree ike this adj[a].push_back(b);
adj[b].push_back(a);
Subscribers don't define the quality of a channel. I went through the depth of a tree using DP by Aditya Verma. That video is giving totally wrong concept. Also, the guy is too egoistic to accept that his method was wrong. Your explanations are good . Just try to make videos on DP on segment trees and Fenwick trees
Stop pitching people who are trying to help us against each other.
Observation: max( dp(1,0) , dp(1,1) ) = dp(1,1) always