fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	public static void main (String[] args) throws java.lang.Exception
  11. 	{
  12. 		Scanner sc= new Scanner(System.in);
  13. 		int tc=sc.nextInt();
  14. 		while(tc-->0){
  15.  
  16.             long n = sc.nextLong();
  17.  
  18.             ArrayList<ArrayList<Long>> G = new ArrayList<>();
  19.             for (int i = 0; i <= n; i++) G.add(new ArrayList<>());
  20.  
  21.             for (long i = 1; i <= n - 1; i++) {
  22.                 long y = sc.nextLong();
  23.                 G.get((int) y).add(i);
  24.             }
  25.  
  26.             ArrayList<Long> l = new ArrayList<>();
  27.             ArrayList<Long> r = new ArrayList<>();
  28.  
  29.             for (int i = 1; i <= n; i++) {
  30.                 long sz = G.get(i).size();
  31.                 if (sz > 0) l.add(sz);
  32.             }
  33.  
  34.             l.add(1L);
  35.  
  36.             long c = l.size();
  37.             Collections.sort(l);
  38.  
  39.             for (int i = 0; i < c; i++) {
  40.                 long diff = l.get(i) - (i + 1);
  41.                 if (diff > 0) r.add(diff);
  42.             }
  43.  
  44.             long answer = 0;
  45.             long ty = 0;
  46.  
  47.             while (ty <= 1000000000L) {
  48.                 long extra = ty;
  49.  
  50.                 for (long val : r) {
  51.                     if (val > ty) extra -= (val - ty);
  52.                 }
  53.  
  54.                 if (extra >= 0) {
  55.                     answer = ty;
  56.                     break;
  57.                 }
  58.  
  59.                 ty++;
  60.             }
  61.  
  62.             System.out.println(c + answer);
  63. 		}
  64. 	}
  65. }
Success #stdin #stdout 0.12s 54492KB
comments (?)
stdin
copy 
5
7
1 1 1 2 2 4
5
5 5 1 4
2
1
3
3 1
6
1 1 1 1 1
stdout
copy 
4
4
2
3
4
https://ideone.com/fMOh0e
language:
Java (HotSpot 12)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!