Hi, I am new to graphs, and I tried the question:
The approach is as follows:
each node will have the maximum sum of its children’s connected components
tempans will be the minimum of that value for the graph, and that will be the answer
#include <iostream>
#include<vector>
#define ll long long
using namespace std;
vector<long long int> arr[100001];
long long int dfs(long long int parent,long long int child){
long long int ans=1;
for(long long int i: arr[child]){
if(i==parent) continue;
else{
ans+=dfs(child, i);
}
}
return ans;
}
int main()
{
long long int t;cin>>t;
while(t--){
long long int n;cin>>n;
for(long long int i=0;i<n;i++) arr[i]={};
for(long long int i=0;i<n-1;i++){
long long int a,b;
cin>>a>>b;
arr[a-1].push_back(b-1);
arr[b-1].push_back(a-1);
}
long long int ans=0, maxi=10000000;
for(long long int i=0;i<n;i++){
long long int temp=0,tempans=0;
for(long long int j=0;j<arr[i].size();j++){
temp=dfs(i,arr[i][j]);
// cout<<"dfs "<<i<<" "<<j<<" "<<temp<<endl;
tempans=max(tempans,temp);
}
if(tempans<maxi) {maxi=tempans; ans=i;}
}
cout<<ans+1<<" "<<maxi<<endl;
}
}