fork download 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class Codechef{
  6.  
  7.     public static void main(String[] args) throws java.lang.Exception
  8.     {
  9.         // your code goes here
  10.         Scanner sc=new Scanner(System.in);
  11.         int t=sc.nextInt();
  12.         while(t-->0){
  13.             int n=sc.nextInt(); 
  14.             ArrayList<ArrayList<Integer>> tree = new ArrayList<>();
  15.             for (int i = 0; i <= n; i++) {
  16.                 tree.add(new ArrayList<>());
  17.             }
  18.             for (int child = 2; child <= n; child++) {
  19.                 int parent = sc.nextInt();
  20.                 tree.get(parent).add(child);
  21.             }
  22.             System.out.println(tree);
  23.             ArrayList<Integer>l=new ArrayList<>();
  24.             ArrayList<Integer>r=new ArrayList<>();
  25.             l.add(1); // root : 1
  26.             for (int node = 1; node <= n; node++) {
  27.                 int count = tree.get(node).size();
  28.                 if (count > 0) {
  29.                     l.add(count);
  30.                 }
  31.             }
  32.  
  33.             int time=0;
  34.             while (!l.isEmpty()) {
  35.                 Collections.sort(l, Collections.reverseOrder());
  36.                 ArrayList<Integer> r1 = new ArrayList<>();
  37.                 for (int x : r) {
  38.                     if (x - 1 > 0) r1.add(x - 1);
  39.                 }
  40.                 r = r1;
  41.                 int max = l.get(0);
  42.                 l.remove(0);
  43.                 if (max - 1 > 0) r.add(max - 1);
  44.                 time++;
  45.             }
  46.  
  47.             // while(!r.isEmpty()){
  48.             //     Collections.sort(r);
  49.             //     for(int i=0;i<r.size();i++){
  50.             //         if(r.get(i)-1==0){
  51.             //             r.remove(i);
  52.             //         }else r.set(i,r.get(i)-1);
  53.             //     }
  54.             //     if(r.size()==0)break;
  55.             //     int max=r.get(r.size()-1);
  56.             //     if(r.get(r.size()-1)-1==0){
  57.             //             r.remove(r.size()-1);
  58.             //         }else r.set(r.size()-1,max-1);
  59.             //     time++;
  60.             // }
  61.             while (!r.isEmpty()) {
  62.                 // sort ascending
  63.                 Collections.sort(r);
  64.                 ArrayList<Integer> r1 = new ArrayList<>();
  65.                 for (int x : r) {
  66.                     if (x - 1 > 0) {
  67.                         r1.add(x - 1);
  68.                     }
  69.                 }
  70.                 r = r1;
  71.                 if (r.isEmpty()) break;
  72.                 Collections.sort(r);
  73.                 int lastIndex = r.size() - 1;
  74.                 int max = r.get(lastIndex);
  75.                 if (max - 1 > 0) {
  76.                     r.set(lastIndex, max - 1);
  77.                 } else {
  78.                     r.remove(lastIndex);
  79.                 }
  80.                 time++;
  81.             }
  82.             System.out.println(time);
  83.         }
  84.     }
  85. }
  86.  
Success #stdin #stdout 0.14s 56496KB
comments (?)
stdin 
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 
[[], [2, 3, 4], [5, 6], [], [7], [], [], []]
4
[[], [4], [], [], [5], [2, 3]]
4
[[], [2], []]
2
[[], [3], [], [2]]
3
[[], [2, 3, 4, 5, 6], [], [], [], [], []]
3
https://ideone.com/nw1mTs
language:
Java (HotSpot 12)
created:
2 days 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!