SHARE
TWEET

CF 253 Div1D

a guest Jun 19th, 2014 231 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class HLD {
  5.     FastScanner in;
  6.     PrintWriter out;
  7.  
  8.     class TwoMax {
  9.         int val1, val2;
  10.  
  11.         TwoMax() {
  12.             val1 = val2 = -1;
  13.         }
  14.  
  15.         void addValue(int value) {
  16.            if (value > val2) {
  17.               val2 = value;
  18.            }
  19.             if (val2 > val1) {
  20.                 int tmp = val1;
  21.                 val1 = val2;
  22.                 val2 = tmp;
  23.             }
  24.         }
  25.     }
  26.  
  27.     int res;
  28.     int[] p;
  29.     boolean[] isLayerTwo;
  30.     int[] dp;
  31.     TwoMax[] t;
  32.  
  33.     void update(int v) {
  34.         if (isLayerTwo[v]) {
  35.             res = Math.max(res, dp[v]);
  36.             return;
  37.         }
  38.         t[p[v]].addValue(dp[v]);
  39.         int newValue = Math.max(t[p[v]].val1, t[p[v]].val2 + 1);
  40.         if (dp[p[v]] != newValue) {
  41.             dp[p[v]] = newValue;
  42.             update(p[v]);
  43.         }
  44.     }
  45.  
  46.     void solve() {
  47.         int n = in.nextInt() + 1;
  48.         p = new int[n];
  49.         t = new TwoMax[n];
  50.         isLayerTwo = new boolean[n];
  51.         dp = new int[n];
  52.         for (int i = 1; i < n; i++) {
  53.             int parent = in.nextInt() - 1;
  54.             if (parent == 0) {
  55.                 isLayerTwo[i] = true;
  56.             } else {
  57.                 p[i] = parent;
  58.             }
  59.             t[i] = new TwoMax();
  60.             dp[i] = 1;
  61.             update(i);
  62.             out.print(res + " ");
  63.         }
  64.     }
  65.  
  66.     void run() {
  67.         try {
  68.             in = new FastScanner(new File("object.in"));
  69.             out = new PrintWriter(new File("object.out"));
  70.  
  71.             solve();
  72.  
  73.             out.close();
  74.         } catch (FileNotFoundException e) {
  75.             e.printStackTrace();
  76.         }
  77.     }
  78.  
  79.     void runIO() {
  80.  
  81.         in = new FastScanner(System.in);
  82.         out = new PrintWriter(System.out);
  83.  
  84.         solve();
  85.  
  86.         out.close();
  87.     }
  88.  
  89.     class FastScanner {
  90.         BufferedReader br;
  91.         StringTokenizer st;
  92.  
  93.         public FastScanner(File f) {
  94.             try {
  95.                 br = new BufferedReader(new FileReader(f));
  96.             } catch (FileNotFoundException e) {
  97.                 e.printStackTrace();
  98.             }
  99.         }
  100.  
  101.         public FastScanner(InputStream f) {
  102.             br = new BufferedReader(new InputStreamReader(f));
  103.         }
  104.  
  105.         String next() {
  106.             while (st == null || !st.hasMoreTokens()) {
  107.                 String s = null;
  108.                 try {
  109.                     s = br.readLine();
  110.                 } catch (IOException e) {
  111.                     e.printStackTrace();
  112.                 }
  113.                 if (s == null)
  114.                     return null;
  115.                 st = new StringTokenizer(s);
  116.             }
  117.             return st.nextToken();
  118.         }
  119.  
  120.         boolean hasMoreTokens() {
  121.             while (st == null || !st.hasMoreTokens()) {
  122.                 String s = null;
  123.                 try {
  124.                     s = br.readLine();
  125.                 } catch (IOException e) {
  126.                     e.printStackTrace();
  127.                 }
  128.                 if (s == null)
  129.                     return false;
  130.                 st = new StringTokenizer(s);
  131.             }
  132.             return true;
  133.         }
  134.  
  135.         int nextInt() {
  136.             return Integer.parseInt(next());
  137.         }
  138.  
  139.         long nextLong() {
  140.             return Long.parseLong(next());
  141.         }
  142.     }
  143.  
  144.     public static void main(String[] args) {
  145.         new HLD().runIO();
  146.     }
  147. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top