➤ Problem Link : 161D. Distance in Tree
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
long long int ans=0;
vector<int> dfs(int v,vector<int> adj[],int p,int k)
{
long long int temp=0;
vector<int> vec(1000,0);
vector<int> t[adj[v].size()+1];
if(adj[v].size()==1 && p!=-1) //leaf
{
vec[0]=1;
return vec;
}
for(int i=0;i<adj[v].size();i++)
{
if(adj[v][i]==p)
continue;
t[i]=dfs(adj[v][i],adj,v,k);
for(int j=0;j<999;j++)
{
vec[j+1]+=t[i][j];
}
}
for(int i=0;i<adj[v].size();i++)
{
if(adj[v][i]==p)
continue;
for(int j=0;j<999;j++)
{
if(k-j-2<0)
break;
temp+=(t[i][j])*(vec[k-j-1]-t[i][k-j-2]);
}
}
vec[0]=1;
ans+=vec[k]+temp/2;
if(v==1)
return vec;
}
int main()
{
int n,k,a,b;
cin>>n>>k;
vector<int> adj[n+1];
for(int i=1;i<n;i++)
{
cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1,adj,-1,k);
cout<<ans<<"\n";
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
➤ Problem Link : 161D. Distance in Tree
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
long long int ans=0;
vector<int> dfs(int v,vector<int> adj[],int p,int k)
{
long long int temp=0;
vector<int> vec(1000,0);
vector<int> t[adj[v].size()+1];
if(adj[v].size()==1 && p!=-1) //leaf
{
vec[0]=1;
return vec;
}
for(int i=0;i<adj[v].size();i++)
{
if(adj[v][i]==p)
continue;
t[i]=dfs(adj[v][i],adj,v,k);
for(int j=0;j<999;j++)
{
vec[j+1]+=t[i][j];
}
}
for(int i=0;i<adj[v].size();i++)
{
if(adj[v][i]==p)
continue;
for(int j=0;j<999;j++)
{
if(k-j-2<0)
break;
temp+=(t[i][j])*(vec[k-j-1]-t[i][k-j-2]);
}
}
vec[0]=1;
ans+=vec[k]+temp/2;
if(v==1)
return vec;
}
int main()
{
int n,k,a,b;
cin>>n>>k;
vector<int> adj[n+1];
for(int i=1;i<n;i++)
{
cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1,adj,-1,k);
cout<<ans<<"\n";
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.