SUBMEXS - Editorial

editorial
, , , , , ,
66

Got AC.
Time 0.13 sec.

Approach :
Calculate and store subtree size of each node in a vector called subtree[i].
While backtraking at each node return subtree[node] + max(value returned by below subtree)…

Please see solution for clear understanding …
https://www.codechef.com/viewsolution/39266674

Thanks

67

Link u have given does not lead to your solution. This is correct link

68

If anybody is facing difficulty in understanding the reason for the solution.
Check my solution, i have added comments to explain the reason.

Solution-Click Here

Draw tree on a paper,it helps in getting a better understanding!

1 Like
69

Take a look, I used the same approach but

70

Thxx

71

@zephxr Editorial was confusing, Thanks for the code with comments.

1 Like
72

Welcome Buddy!

73

My code is not passing 1 and 2 test cases. Anyone can help me, please?

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 5;
vector adj[MAX];
long long cnt[MAX];
long long size[MAX];
void dfs(int i,int p)
{
cnt[i] = -1;
size[i] = 1;
for(int k=0;k<adj[i].size();k++)
{
int node = adj[i][k];

   if(node==p) continue;
   
   dfs(node,i);
   
   size[i] += size[node];
   cnt[i] = max(cnt[i],cnt[node]);

}
if(adj[i].size()>1)
cnt[i] += size[i];
else
cnt[i] = 1;

}
void init()
{
for(int i=0;i<MAX;i++)
{
adj[i].clear();
size[i]=0;
cnt[i]=0;
}
}
int main()
{

ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
   int n;
   cin>>n;
   init();
   for(int i=1;i<n;i++)
   {
       int x;
       cin>>x;
       adj[x].push_back(i+1);
       adj[i+1].push_back(x);
   }
  
  dfs(1,-1);    
  
  cout<<cnt[1]<<endl;
    
}

return 0;

}

1 Like
75

Below is my code ,O(n) solution .But it is passing only first testcase and TLE in rest .Please let me know why is it so !

#include
#include
#include
#define lli long long int
using namespace std;

int size[100001];
int vis[100001];
lli final[100001];
void dfs(int s,vector<vector > adj)
{
if(vis[s] == 0) vis[s] = 1;
int max = -1;
for(int i =0;i<adj[s].size();i++)
{
int child = adj[s][i];
if(vis[child] == 0)
{
dfs(child,adj);
size[s]+=size[child];
if(final[child]>max) max = final[child];

	}
	if(max!= -1)
	final[s]=max + size[s];
}

}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int T;
scanf("%d",&T);
while(T--)
{
	int N,p;
	scanf("%d",&N);
	
	vector<vector<int > > adj(N+1);
	size[1] = 1;
	vis[1] = 0;
	final[1] = 1;
	for(int i =2;i<=N;i++)
	{
		size[i] = 1;
		vis[i] = 0;
		final[i] = 1;
		scanf("%d",&p);
		adj[p].push_back(i);
		adj[i].push_back(p);
	}
	dfs(1,adj);
	printf("%lld\n",final[1]);
}
return 0;

}

76

nice man what a nice test cases…
Thanks for this. which clearly breaks greedy approach… thanks