Chef and Subtree MEXs Solution SUBMEXS

by

Chef and Subtree MEXs Codechef Solution

The MEX of a set of integers is defined as the smallest non-negative integer that does not belong to this set. For example, MEX({0,2,3})=1 and MEX({1,3})=0.

Chef has a tree with N nodes (numbered 1 through N). The tree is rooted at node 1. Chef wants to assign a non-negative integer to each node in such a way that each integer between 0 and N−1 (inclusive) is assigned to exactly one node.

For each node u, consider the integers assigned to the nodes in the subtree of u (including u); let au denote the MEX of these integers. Chef wants a1+a2+…+aN to be as large as possible. Find the maximum possible value of this sum.

Input

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains a single integer N.

The second line contains N−1 space-separated integers p1,p2,…,pN−1. For each valid i, the node pi is the parent of the node i+1.

Output

For each test case, print a single line containing one integer ― the maximum sum of subtree MEX-s which can be obtained if you assign the weights optimally.

Constraints

1≤T≤5

2≤N≤105

1≤pi<i for each valid i

Subtasks

Subtask #1 (100 points): original constraints

Example Input

2

3

1 1

5

1 1 2 2

Example Output

4

9

Solution

Program Python:

import sys
input,print=sys.stdin.readline,sys.stdout.write
sys.setrecursionlimit(10**6)
def ans(dic,n):
    if dic.get(n)!=None:
        b=[]
        for a in dic[n]:
            b.append(ans(dic,a))
        mx=0 
        node=0
        for a in b:
            if a[0]>mx:
                mx=a[0]
            node+=a[1]
        node+=len(dic[n])
        return (mx+node+1,node)
    else:
        return (1,0)
        
for i in range(int(input())):
    n=int(input())
    a=[int(x) for x in input().split()]
    dic={}
    for j in range(1,n):
        temp=a[j-1]
        if dic.get(temp)==None:
            dic[temp]=[j+1]
        else:
            dic[temp].append(j+1)
    anss=ans(dic,1)
    print(str(anss[0])+"\n")

Program C++:

#include <bits/stdc++.h>
using namespace std;
vector<int> v[100005];
pair<long long,int> dfs(int node)
{
	long long mx=0;
	int sz=1;
	for (int u:v[node])
	{
		auto tmp=dfs(u);
		mx=max(mx,tmp.first);
		sz+=tmp.second;
	}
	return {mx+sz,sz};
}
int main()
{
	int t;
	scanf("%d",&t);
	while (t--)
	{
		int n;
		scanf("%d",&n);
		for (int i=1;i<=n;i++)
		v[i].clear();
		for (int i=2;i<=n;i++)
		{
			int p;
			scanf("%d",&p);
			v[p].push_back(i);
		}
		printf("%lld\n",dfs(1).first);
	}
	return 0;
}

Program Java:

import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{
    public static int[] childcount;
    public static long[] cumulcount;
    static long countcumul(ArrayList<ArrayList<Integer>> adj,int node)
    {
        if(adj.get(node).size()==0)
        {
            cumulcount[node]=1;
            return 1; 
        }
        if(cumulcount[node]!=0)
        return cumulcount[node];
        long count=childcount[node];
        
        int maxindex=-1;
        long maxcount=-1;
        for(int i:adj.get(node))
        {
                
            long cost=countcumul(adj,i);
            if(cost>maxcount)
            {
                maxindex=i;
                maxcount=cost;
            }
               
        }
        count+=maxcount;
        
        
        cumulcount[node]=count;
        return count;
    }
    static int countchildren(ArrayList<ArrayList<Integer>> adj,int node)
    {
        if(adj.get(node).size()==0)
        {
            childcount[node]=1;
            return 1; 
        }
        if(childcount[node]!=0)
        return childcount[node];
        int count=1;
        for(int i:adj.get(node))
        {
            count+=countchildren(adj,i);
        }
        childcount[node]=count;
        return count;
    }
	public static void main (String[] args) throws java.lang.Exception
	{
	    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	    int t=Integer.parseInt(br.readLine().trim());
	    for(int q=0;q<t;q++)
	    {
	       int n=Integer.parseInt(br.readLine().trim());
	       childcount=new int[n+1];
	       cumulcount=new long[n+1];
	       ArrayList<ArrayList<Integer>> adj=new ArrayList<>();
	       for(int i=0;i<=n;i++)
	       {
	           adj.add(new ArrayList<>());
	       }
	       StringTokenizer st=new StringTokenizer(br.readLine());
	       for(int i=1;i<n;i++)
	       {
	           int parent=Integer.parseInt(st.nextToken());
	           adj.get(parent).add(i+1);
	       }
	       countchildren(adj,1);
	       countcumul(adj,1);
	       int maxcount=n;
	       int i=1;
	       
	       System.out.println(cumulcount[1]);
	       
	    }
		// your code goes here
	}
}

Codechef Long Challenge

November Long Challenge 2020 Codechef Solution

October Lunchtime 2020 Codechef Solutions

Leave a Comment