➤ Problem Link : RTREE
👉 Hint : Use DFS
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
vector<int> arr[100002];
bool visited[100002];
int ans[100002];
pair<int,int> dfsLong(int v)
{
int max1=0;
int max2=0;
pair<int,int> child;
int val=0;
visited[v]=1;
if(arr[v].size()==0)
return make_pair(1,1);
for(int i=0;i<arr[v].size();i++)
{
if(!visited[arr[v][i]])
{
child=dfsLong(arr[v][i]);
if(child.second>max1)
{
max2=max1;
max1=child.second;
}
else if(child.second>max2)
max2=child.second;
val=max(val,child.first);
}
}
val=max(val,1+max1+max2);
ans[v]=val-1;
return make_pair(val,1+max1);
}
int main()
{
int u,v,n,r,q,s;
cin>>n;
memset(arr,0,sizeof(arr));
memset(visited,0,sizeof(visited));
for(int i=1;i<n;i++)
{
cin>>u>>v;
arr[u].push_back(v);
arr[v].push_back(u);
}
cin>>r;
dfsLong(r).first;
cin>>q;
while(q--)
{
cin>>s;
cout<<ans[s]<<endl;
}
}
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.