AtCoder Beginner Contest 428 E

https://atcoder.jp/contests/abc428/tasks/abc428_e

木の直径は、適当な点Aから最も遠い点Bを探して、さらに点Bから最も遠い点Cを探します。BとCの距離が直径です。そして、BとCから直径の半分の距離の点があるのでその点Mが木中点です（距離が奇数ならBとCからの距離が1違いになります）。点Mの隣の点から繋がっている領域に分けることができます。その中で点Mから最も遠い点を含む領域D1と次に遠い点を含む領域D2とすると、D1の領域の点からは最も遠い点はD2の最も遠い点。それ以外の点はD1の最も遠い点になります。

// Farthest Vertex
#![allow(non_snake_case)]

use std::cmp::max;
use std::collections::VecDeque;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Graph ////////////////////

type Node = usize;
type Edge = (Node, Node);

fn read_edge() -> Edge {
    let v: Vec<Node> = read_vec();
    (v[0] - 1, v[1] - 1)
}

struct Graph {
    g: Vec<Vec<Node>>
}

impl Graph {
    // 最も遠い節点と各節点までの距離
    fn dists(&self, v0: Node) -> (Node, Vec<i32>)  {
        let N = self.g.len();
        let mut ds: Vec<i32> = vec![-1; N];
        ds[v0] = 0;
        let mut q: VecDeque<(Node, i32)> = VecDeque::new();
        q.push_back((v0, 0));
        let mut last_node = v0;
        while let Some((v, d)) = q.pop_front() {
            last_node = v;
            for &w in self.g[v].iter() {
                if ds[w] == -1 {
                    ds[w] = d + 1;
                    q.push_back((w, d + 1))
                }
            }
        }
        (last_node, ds)
    }
    
    fn read(N: usize, M: usize) -> Graph {
        let mut g: Vec<Vec<Node>> = vec![vec![]; N];
        for _ in 0..M {
            let (U, V) = read_edge();
            g[U].push(V);
            g[V].push(U)
        }
        for v in 0..N {
            g[v].sort()
        }
        Graph { g }
    }
}

//////////////////// process ////////////////////

// 木の中心
fn mid_point(graph: &Graph) -> Node {
    let N = graph.g.len();
    let (v1,   _) = graph.dists(0);
    let (v2, ds1) = graph.dists(v1);
    let (_,  ds2) = graph.dists(v2);
    // v1とv2まで等距離の節点を見つける
    // ただし、木の直径が奇数なら、一つ違いになる
    let max_dist = ds1[v2];
    let d1 = max_dist / 2;
    let d2 = max_dist - d1;
    let mid = (0..N).filter(|&v| ds1[v] == d1 && ds2[v] == d2).next().unwrap();
    mid
}

// 木の中心から各枝への最も遠い距離とその枝から辿れる節点を求める
fn dists_from_mid(mid: Node, graph: &Graph) -> Vec<(i32, Node, Vec<Node>)> {
    let N = graph.g.len();
    let mut dists: Vec<(i32, Node, Vec<Node>)> = vec![];
    let mut ds: Vec<i32> = vec![-1; N];
    ds[mid] = 0;
    for &v0 in graph.g[mid].iter() {
        let mut q: VecDeque<(Node, i32)> = VecDeque::new();
        q.push_back((v0, 1));
        ds[v0] = 1;
        let mut farthest_node = (1, v0);
        let mut vs: Vec<Node> = vec![];
        while let Some((v, d)) = q.pop_front() {
            farthest_node = max((d, v), farthest_node);
            vs.push(v);
            for &w in graph.g[v].iter() {
                if ds[w] == -1 {
                    ds[w] = d + 1;
                    q.push_back((w, d + 1))
                }
            }
        }
        dists.push((farthest_node.0, farthest_node.1, vs))
    }
    dists
}

fn F(N: usize) {
    let graph = Graph::read(N, N-1);
    let mid = mid_point(&graph);
    // 木の中心から伸びる枝ごとに、最も遠い節点までの距離を求める
    let mut dists = dists_from_mid(mid, &graph);
    dists.sort_by_key(|a| (a.0, a.1));
    let M = dists.len();
    
    let mut farthests: Vec<Node> = vec![0; N];
    farthests[mid] = dists[M-1].1;
    for i in 0..M {
        let j = if i == M-1 { M-2 } else { M-1 };
        for &v in dists[i].2.iter() {
            farthests[v] = dists[j].1
        }
    }
    for v in 0..N {
        println!("{}", farthests[v] + 1)
    }
}

fn main() {
    let N: usize = read();
    F(N)
}