Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- public class HLD {
- FastScanner in;
- PrintWriter out;
- class TwoMax {
- int val1, val2;
- TwoMax() {
- val1 = val2 = -1;
- }
- void addValue(int value) {
- if (value > val2) {
- val2 = value;
- }
- if (val2 > val1) {
- int tmp = val1;
- val1 = val2;
- val2 = tmp;
- }
- }
- }
- int res;
- int[] p;
- boolean[] isLayerTwo;
- int[] dp;
- TwoMax[] t;
- void update(int v) {
- if (isLayerTwo[v]) {
- res = Math.max(res, dp[v]);
- return;
- }
- t[p[v]].addValue(dp[v]);
- int newValue = Math.max(t[p[v]].val1, t[p[v]].val2 + 1);
- if (dp[p[v]] != newValue) {
- dp[p[v]] = newValue;
- update(p[v]);
- }
- }
- void solve() {
- int n = in.nextInt() + 1;
- p = new int[n];
- t = new TwoMax[n];
- isLayerTwo = new boolean[n];
- dp = new int[n];
- for (int i = 1; i < n; i++) {
- int parent = in.nextInt() - 1;
- if (parent == 0) {
- isLayerTwo[i] = true;
- } else {
- p[i] = parent;
- }
- t[i] = new TwoMax();
- dp[i] = 1;
- update(i);
- out.print(res + " ");
- }
- }
- void run() {
- try {
- in = new FastScanner(new File("object.in"));
- out = new PrintWriter(new File("object.out"));
- solve();
- out.close();
- } catch (FileNotFoundException e) {
- e.printStackTrace();
- }
- }
- void runIO() {
- in = new FastScanner(System.in);
- out = new PrintWriter(System.out);
- solve();
- out.close();
- }
- class FastScanner {
- BufferedReader br;
- StringTokenizer st;
- public FastScanner(File f) {
- try {
- br = new BufferedReader(new FileReader(f));
- } catch (FileNotFoundException e) {
- e.printStackTrace();
- }
- }
- public FastScanner(InputStream f) {
- br = new BufferedReader(new InputStreamReader(f));
- }
- String next() {
- while (st == null || !st.hasMoreTokens()) {
- String s = null;
- try {
- s = br.readLine();
- } catch (IOException e) {
- e.printStackTrace();
- }
- if (s == null)
- return null;
- st = new StringTokenizer(s);
- }
- return st.nextToken();
- }
- boolean hasMoreTokens() {
- while (st == null || !st.hasMoreTokens()) {
- String s = null;
- try {
- s = br.readLine();
- } catch (IOException e) {
- e.printStackTrace();
- }
- if (s == null)
- return false;
- st = new StringTokenizer(s);
- }
- return true;
- }
- int nextInt() {
- return Integer.parseInt(next());
- }
- long nextLong() {
- return Long.parseLong(next());
- }
- }
- public static void main(String[] args) {
- new HLD().runIO();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement