Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.lang.*;
- import java.util.*;
- public class biarylifting {
- static class FastScanner {
- InputStreamReader is;
- BufferedReader br;
- StringTokenizer st;
- public FastScanner() {
- is = new InputStreamReader(System.in);
- br = new BufferedReader(is);
- }
- String next() throws Exception {
- while (st == null || !st.hasMoreElements())
- st = new StringTokenizer(br.readLine());
- return st.nextToken();
- }
- int nextInt() throws Exception {
- return Integer.parseInt(next());
- }
- long nextLong() throws Exception {
- return Long.parseLong(next());
- }
- int[] readArray(int num) throws Exception {
- int arr[]=new int[num];
- for(int i=0;i<num;i++)
- arr[i]=nextInt();
- return arr;
- }
- String nextLine() throws Exception {
- return br.readLine();
- }
- }
- public static boolean power_of_two(int a)
- {
- if((a&(a-1))==0)
- {
- return true;
- }
- return false;
- }
- static ArrayList<Integer> tr[]=new ArrayList[200001]; // COCONUT TREE
- public static void display(int parent) // displaying the COCONUTS
- {
- if(tr[parent]==null)
- {
- System.out.println(parent);
- return;
- }
- System.out.println(parent);
- for(int i:tr[parent])
- {
- display(i);
- }
- }
- public static void add(int parent, int child) // ADDING COCONUTS TO THE TREE
- {
- if(tr[parent]==null)
- {
- ArrayList<Integer> x=new ArrayList<>();
- tr[parent]=x;
- }
- if(tr[child]==null)
- {
- ArrayList<Integer> x=new ArrayList<>();
- tr[child]=x;
- }
- tr[parent].add(child);
- }
- static int dp[][]=new int[200001][20];
- public static void binary(int src, int par) // THIS IS BINARY LIFTING , BUT NO USE IN THIS QUESTION
- {
- dp[src][0]=par;
- for(int i=1;i<20;i++)
- {
- if(dp[src][i-1]!=-1)
- {
- dp[src][i]=dp[dp[src][i-1]][i-1];
- }
- else{
- dp[src][i-1]=-1;
- }
- }
- for(int child:tr[src])
- {
- if(tr[child]!=null)
- {
- binary(child,src);
- }
- }
- }
- public static int query(int node, int jump) // BINAR... LIF...
- {
- if(node==-1 || jump==0)
- {
- return node;
- }
- for(int i=19;i>=0;i--)
- {
- if(jump>=(1<<i))
- {
- ans= query(dp[node][i],jump-(1<<i));
- }
- }
- return ans;
- }
- static int ans;
- static int ar[];
- public static void main(String args[]) throws java.lang.Exception
- {
- FastScanner sc=new FastScanner();
- int n=sc.nextInt();
- tr=new ArrayList[200001];
- for(int i=2;i<=n;i++)
- {
- int parent=sc.nextInt();
- add(parent,i);
- }
- ar=new int[n+1];
- find(tr,ar,1);
- for(int i=1;i<=n;i++)
- {
- System.out.print(ar[i]+" ");
- }
- }
- public static void find(ArrayList<Integer> tr[],int ar[],int i)
- {
- for(int j=0;j<tr[i].size();j++)
- {
- find(tr,ar,tr[i].get(j));
- ar[i]+=ar[tr[i].get(j)];
- }
- ar[i]+=tr[i].size();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement