Advertisement
Nevada112

c s e s

May 10th, 2021 (edited)
1,296
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5 2.89 KB | None | 0 0
  1. import java.io.*;
  2. import java.lang.*;
  3. import java.util.*;
  4. public class biarylifting {
  5. static class FastScanner {
  6. InputStreamReader is;
  7. BufferedReader br;
  8. StringTokenizer st;
  9. public FastScanner() {
  10. is = new InputStreamReader(System.in);
  11. br = new BufferedReader(is);
  12. }
  13. String next() throws Exception {
  14. while (st == null || !st.hasMoreElements())
  15. st = new StringTokenizer(br.readLine());
  16. return st.nextToken();
  17. }
  18. int nextInt() throws Exception {
  19. return Integer.parseInt(next());
  20. }
  21. long nextLong() throws Exception {
  22. return Long.parseLong(next());
  23. }
  24. int[] readArray(int num) throws Exception {
  25. int arr[]=new int[num];
  26. for(int i=0;i<num;i++)
  27. arr[i]=nextInt();
  28. return arr;
  29. }
  30. String nextLine() throws Exception {
  31. return br.readLine();
  32. }
  33. }
  34.  public static boolean power_of_two(int a)
  35. {
  36.   if((a&(a-1))==0)
  37. {
  38.  return true;
  39. }
  40. return false;
  41. }
  42.  
  43. static ArrayList<Integer> tr[]=new ArrayList[200001];      //  COCONUT TREE
  44.  
  45.  
  46. public static void display(int parent)                 // displaying the COCONUTS
  47. {
  48.     if(tr[parent]==null)
  49.     {
  50.         System.out.println(parent);  
  51.         return;
  52.     }
  53.     System.out.println(parent);
  54.     for(int i:tr[parent])
  55.     {
  56.         display(i);
  57.     }
  58. }
  59.  
  60. public static void add(int parent, int child)          // ADDING COCONUTS TO THE TREE
  61. {
  62.     if(tr[parent]==null)
  63.     {
  64.  ArrayList<Integer> x=new ArrayList<>();
  65.  tr[parent]=x;
  66.     }
  67.     if(tr[child]==null)
  68.     {
  69.  ArrayList<Integer> x=new ArrayList<>();
  70.     tr[child]=x;
  71.     }
  72. tr[parent].add(child);
  73. }
  74. static int dp[][]=new int[200001][20];
  75.  
  76. public static void binary(int src, int par)               // THIS IS BINARY LIFTING , BUT NO USE IN THIS QUESTION
  77. {
  78.     dp[src][0]=par;
  79.     for(int i=1;i<20;i++)
  80.     {
  81.         if(dp[src][i-1]!=-1)
  82.         {
  83.             dp[src][i]=dp[dp[src][i-1]][i-1];
  84.         }
  85.         else{
  86.             dp[src][i-1]=-1;
  87.         }
  88.     }
  89.     for(int child:tr[src])
  90.     {
  91.         if(tr[child]!=null)
  92.         {
  93.             binary(child,src);
  94.         }
  95.     }
  96. }
  97.  
  98. public static int query(int node, int jump)         // BINAR... LIF...
  99. {
  100.     if(node==-1 || jump==0)
  101.     {
  102.         return node;
  103.     }
  104.     for(int i=19;i>=0;i--)
  105.     {
  106.         if(jump>=(1<<i))
  107.         {
  108.          ans= query(dp[node][i],jump-(1<<i));
  109.         }
  110.     }
  111.     return ans;
  112. }
  113. static int ans;
  114. static int ar[];
  115. public static void main(String args[]) throws java.lang.Exception
  116. {
  117. FastScanner sc=new FastScanner();
  118. int n=sc.nextInt();
  119. tr=new ArrayList[200001];
  120.  for(int i=2;i<=n;i++)
  121.  {
  122.      int parent=sc.nextInt();
  123.      add(parent,i);
  124.  }
  125.  
  126. ar=new int[n+1];
  127. find(tr,ar,1);
  128. for(int i=1;i<=n;i++)
  129. {
  130.     System.out.print(ar[i]+" ");
  131. }
  132. }
  133.  public static void find(ArrayList<Integer> tr[],int ar[],int i)
  134.  {
  135.      for(int j=0;j<tr[i].size();j++)
  136.      {
  137.          find(tr,ar,tr[i].get(j));
  138.          ar[i]+=ar[tr[i].get(j)];
  139.      }
  140.      ar[i]+=tr[i].size();
  141.  }
  142. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement