Yesterday, I gave the contest “Devil code” on gfg ,
so here is one of the toughest question in the contest -
“Practice | GeeksforGeeks | A computer science portal for geeks”
What I thought is ,we have to find max sum subtree by taking each vertex as a node, and print max value but it will be N2 , so it will give TLE.
void SubtreeSize_DFS(vi adj[] , lli src , vi &sub_size , vbool &vis )
{
vis[src] =1;
sub_size[src] = 1;
for(auto xt : adj[src])
{
if(!vis[xt])
{
SubtreeSize_DFS(adj , xt,sub_size , vis);
sub_size[src] += sub_size[xt];
}
}
}
int main(){
fastio
lli t=1;
cin>>t;
chandan2();
while(t--) {
lli n;
cin>>n;
vi adj[n+1];
lli maxi = -1;
lli x,y;
loop(i,n-1){
cin>>x>>y;
adj[x].pb(y);
adj[y].pb(x);
}
for(lli i=1;i<=n;i++)
{
vi arr(n+1,0);
lli sum= 0 ;
vbool vis(n+1 , false);
SubtreeSize_DFS(adj , i , arr , vis);
FOR(i,1,n+1)
sum+=arr[i];
maxi = max(maxi , sum);
}
print(maxi);
}
return 0;
}
How can I optimize this, please explain approach, technique, algorithm, and if this is something which I don’t know like some other higher concept then please suggest resources too.
@carre @galencolin @ssjgz @l_returns @aneee004 @everule1 @aryan12 @bohdan