Page Contents
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
- Ada and Dishes SOLUTION ADADISH
- Iron Magnet and Wall SOLUTION FEMA2
- Magical Candy Store SOLUTION CNDYGAME
- Unusual Queries SOLUTION UNSQUERS
- Red-Black Boolean Expression SOLUTION RB2CNF
- Chef and the Combination Lock SOLUTION CHEFSSM
- Scalar Product Tree SOLUTION SCALSUM
- Connect on a Grid (Challenge) SOLUTION CONGRID
- Selecting Edges SOLUTION SELEDGE
- Panic! at the Disco SOLUTION PANIC
- Restore Sequence SOLUTION RESTORE
October Lunchtime 2020 Codechef Solutions
- AND Plus OR SOLUTION ANDOR
- Chef and Subtree MEXs SOLUTION SUBMEXS
- Chef Likes Good Sequences SOLUTION GSUB
- Cute Chef Gift SOLUTION COPAR
- Chef Is Just Throwing Random Words SOLUTION SSO
- Counting Spaghetti SOLUTION CDSUMS
- Chef and Edge Flipping SOLUTION EFLIP