My approach:
Calculate and store the size of subtree for each node. Initialize DP array.
dp[1] = subtreeSize[1]
Starting from root node, start BFS:
dp[children] = dp[parent] + subtreeSize[children]
The answer will be maximum of the DP array.
My solution in Java: https://www.codechef.com/viewsolution/39223219
I have also the same problem. I checked with an AC code, answer was 23 only. Now figuring out why?
my solution is in o(n ) but it still gives tle can any one please help
#include <bits/stdc++.h>
#define int long long int
#define MOD 1000000000+ 7
#define pb push_back
//memset(a,1,sizeof(a));
using namespace std;
int cnt=0;
int binPow(int a, int n) {
int res = 1;
while (n) {
if (n & 1)
res = (1LL * res * a) % MOD;
a = (1LL * a * a) % MOD;
n >>= 1;
}
return res;
}
int numc(int x,int nc[],vector v[])
{
if(v[x].size()==0)
{
return 0;
}
int ans=0;
for(int i=0;i<v[x].size();i++)
{
ans+=numc(v[x][i],nc,v)+1;
}
nc[x]=ans;
return ans;
}
int dfs(int x,int visited[],int cnt[],int nc[],int N,vector p,vector v[])
{
visited[x]=1;
cnt[x]=nc[x]+1+cnt[p[x]];
for(int i=0;i<v[x].size();i++)
{
if(visited[v[x][i]]==0)
{
dfs(v[x][i],visited,cnt,nc,N,p,v);
}
}
}
main()
{
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
vector p;
p.pb(0);
p.pb(1);
for(int i=1;i<=n-1;i++)
{
int x;
cin>>x;
p.pb(x);
}
vector v[n+1];
for(int i=2;i<=n;i++)
{
v[p[i]].pb(i);
}
int cnt[n+1]={0};
int nc[n+1]={0};
numc(1,nc,v);
/* for(int i=1;i<=n;i++)
{
cout<<nc[i]<< " ";
}*/
int visited[n+1]={0};
dfs(1,visited,cnt,nc,n,p,v);
sort(cnt,cnt+n+1);
cout<<cnt[n]<<endl;
}
}
i did same but its giving tle can you ols help
#include <bits/stdc++.h>
#define int long long int
#define MOD 1000000000+ 7
#define pb push_back
//memset(a,1,sizeof(a));
using namespace std;
int cnt=0;
int binPow(int a, int n) {
int res = 1;
while (n) {
if (n & 1)
res = (1LL * res * a) % MOD;
a = (1LL * a * a) % MOD;
n >>= 1;
}
return res;
}
int numc(int x,int nc[],vector v[])
{
if(v[x].size()==0)
{
return 0;
}
int ans=0;
for(int i=0;i<v[x].size();i++)
{
ans+=numc(v[x][i],nc,v)+1;
}
nc[x]=ans;
return ans;
}
int dfs(int x,int visited[],int cnt[],int nc[],int N,vector p,vector v[])
{
visited[x]=1;
cnt[x]=nc[x]+1+cnt[p[x]];
for(int i=0;i<v[x].size();i++)
{
if(visited[v[x][i]]==0)
{
dfs(v[x][i],visited,cnt,nc,N,p,v);
}
}
}
main()
{
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
vector p;
p.pb(0);
p.pb(1);
for(int i=1;i<=n-1;i++)
{
int x;
cin>>x;
p.pb(x);
}
vector v[n+1];
for(int i=2;i<=n;i++)
{
v[p[i]].pb(i);
}
int cnt[n+1]={0};
int nc[n+1]={0};
numc(1,nc,v);
/* for(int i=1;i<=n;i++)
{
cout<<nc[i]<< " ";
}*/
int visited[n+1]={0};
dfs(1,visited,cnt,nc,n,p,v);
sort(cnt,cnt+n+1);
cout<<cnt[n]<<endl;
}
}
numc is number of all child i.e directly on indirectly connected below any vertex;
My solution is getting AC on 1, 4 & 5 but is gettin RE in 2 & 3. Could someone help what is the problem with my approach?
from sys import stdin
readline, writeline = stdin.readline, stdin.write
class Graph:
def __init__(self):
self.nnodes = 1
self.count = 1
self.children = []
def dfs(node):
mxc = 1
for next in adj[node].children:
dfs(next)
adj[node].nnodes += adj[next].nnodes
mxc = max(mxc, adj[next].count)
if adj[node].children:
adj[node].count = adj[node].nnodes + mxc
def addEdge(a, b):
adj[a].children.append(b)
for _ in range(int(readline())):
n = int(readline())
a = list(map(int, readline().split()))
adj = [Graph() for i in range(n+3)]
for i, p in enumerate(a):
addEdge(p, i+2)
dfs(1)
writeline("{}\n".format(adj[1].count))kanisht , Your code and approach is very elegant and classy, easy to understand. Thanks bro understood everything. I would recommend this sol. for all beginners who find this question and sol. difficult to understand.
My approach was about the same but, I didn’t allocate mexes and my code got the sample testcases passed, but somehow on submission it only pasess one out of five-six sub tasks.
What’s wrong with this:
CodeChef: Practical coding for everyone
4/5 test cases are passing though I have used the same approach.
Solution link - https://www.codechef.com/submit/complete/39253778
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define sz(v) (int)v.size()
const int MAX = 1e5 + 5;
vector<int> adj[MAX], subsz(MAX), mexSum(MAX);
//Calculating subtree size
void dfs(int ch, int p = -1){
subsz[ch] = 1;
mexSum[ch] = 0;
for(int x : adj[ch]){
if(x == p){
continue;
}else{
dfs(x, ch);
subsz[ch] += subsz[x];
}
}
}
// Calculating mex sum.
void dfs1(int ch, int p = -1){
if(sz(adj[ch]) == 1 && adj[ch][0] == p){
mexSum[ch] = 1;
}
int ans = 0;
for(int x : adj[ch]){
if(p == x)
continue;
dfs1(x, ch);
ans = max(ans, mexSum[x]);
}
mexSum[ch] = ans + subsz[ch];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.in","r",stdin);
freopen("output.in","w",stdout);
#endif
int t=1;
cin>>t;
while(t--){
int n;
cin >> n;
for(int i = 2; i <= n; i++){
int x;
cin >> x;
adj[x].push_back(i);
adj[i].push_back(x);
}
dfs(1);
dfs1(1);
cout << mexSum[1] << endl;
for(int i = 0; i <=n; i++)
adj[i].clear();
}
return 0;
}
I have tried to debug many times but still don’t what is the problem.
@psychik Can you please look into it?
I see… thanks a lot! I got frustrated that I couldn’t solve it and then just gave up 
should’ve looked at it properly.
Did anyone see the video tutorial, I think explanation in video tutorial is not correct from [17:01] to [19:20]. We get pairs( 0+1, 1) from both nodes 2 and 3 . Since our loop runs for two times, ‘s’ will be s+2=3, and maximum m will be 1, And hence from node 1 , pair ( 1+3 =4 , 3) will be returned not (4,2).
My code is passing 4/5 testcases. Please help me find the bug in my code.
https://www.codechef.com/viewsolution/39255623
I tried stress testing with AC codes but all of them were matching with my answers. Probably testcase generator is not producing the corner testcase.
You have initialized ‘m’ as int m=-1 … m should be long long that is the only glitch I see in your solution.
Wow thank you very much that solved my problem. I was more focused on finding a corner case. Indeed it was a overflow case.
It is not optimal to greedily choose the next node with maximum subtree size
because we don’t know what will be the subtree sizes of coming nodes.
example:
1
10
1 1 3 3 3 3 2 8 9
Draw the tree for this testcase ,you will see that according to your logic we went to the node having max subtree size from root but it was optimal to go to the node with smaller subtree size.(Therefore we have to check all possibilities)
Here is my commented AC code:
https://www.codechef.com/viewsolution/39256390
https://www.codechef.com/viewsolution/39258537
Please help me out. I am getting RE in 2 out of 5 test cases. In the rest 3 I am getting AC verdict.
I think bottom most approach won’t work all the time
https://www.codechef.com/viewsolution/39257498
Can anyone tell me , what am I doing wrong, I am getting TLE on 4 test cases and AC in one .