Submission #70268852

---

Source Code Expand

import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;


public class Main implements Runnable {

    int n;
    List<List<Integer>> g = new ArrayList<>();
    int[][] end;
    int[] res;

    int cmp(int[] a, int[] b) {
        int c = Integer.compare(a[0], b[0]);
        if (c != 0) {
            return c;
        } else {
            return Integer.compare(a[1], b[1]);
        }
    }

    void dfs1(int i, int p) {
        end[0][i] = -1;
        end[1][i] = i;
        for (Integer ch : g.get(i)) {
            if (ch == p) continue;
            dfs1(ch, i);

            if (end[0][ch] > end[0][i] || (end[0][ch] == end[0][i] && end[1][ch] > end[1][i])) {
                end[0][i] = end[0][ch];
                end[1][i] = end[1][ch];
            }
        }
        end[0][i]++;
    }

    void dfs2(int i, int p, int pend0, int pend1) {
//        int[][] mx = new int[2][2];
//        mx[0][0] = pend0;
//        mx[0][1] = pend1;
        int mx00 = pend0;
        int mx01 = pend1;
        int mx10 = 0;
        int mx11 = 0;

        for (Integer ch : g.get(i)) {
            if (ch == p) continue;
//            if (cmp(end[ch], mx[0]) > 0) {
//                mx[1] = mx[0];
//                mx[0] = end[ch];
//            } else if (cmp(end[ch], mx[1]) > 0) {
//                mx[1] = end[ch];
//            }
            if (end[0][ch] > mx00 || (end[0][ch] == mx00 && end[1][ch] > mx01)) {
                mx10 = mx00;
                mx11 = mx01;
                mx00 = end[0][ch];
                mx01 = end[1][ch];
            } else if (end[0][ch] > mx10 || (end[0][ch] == mx10 && end[1][ch] > mx11)) {
                mx10 = end[0][ch];
                mx11 = end[1][ch];
            }
        }
        res[i] = mx01 + 1;
//        int[] np1 = new int[] {mx10 + 1, mx11};
//        int[] np2 = new int[] {mx00 + 1, mx01};
        for (Integer ch : g.get(i)) {
            if (ch == p) continue;
            if (mx01 == end[1][ch]) {
                dfs2(ch, i, mx10 + 1, mx11);
            } else {
                dfs2(ch, i, mx00 + 1, mx01);
            }
        }
    }

    public void solve() {
        n = nextInt();
        end = new int[2][n];
        res = new int[n];
        for (int i = 0; i < n; i++) {
            g.add(new ArrayList<>());
        }
        for (int i = 0; i < n - 1; i++) {
            int a = nextInt() - 1, b = nextInt() - 1;
            g.get(a).add(b);
            g.get(b).add(a);
        }
        dfs1(0, -1);
        dfs2(0, -1, -1, 0);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(res[i]);
            if (i < n - 1) sb.append("\n");
        }
        out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        new Thread(null, new Main(), "CustomThread", 1024 * 1024 * 100).start();
    }

    @Override
    public void run() {
        int t = 1;
        for (int i = 0; i < t; i++) {
            new Main().solve();
        }
        out.flush();
    }

    static PrintWriter out = new PrintWriter(System.out, false);
    static InputReader in = new InputReader(System.in);
    static String next() { return in.next(); }
    static int nextInt() { return Integer.parseInt(in.next()); }
    static long nextLong() { return Long.parseLong(in.next()); }
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
    }
}

Submission Info

Judge Result