AtCoder Beginner Contest 437 E

https://atcoder.jp/contests/abc437/tasks/abc437_e

Vec<Vec<Vec<usize>>>で木を実現します。
入力例1なら、最初にxが0を探します。そうすると、2番目と4番目のyが1で、1番目のyが2なので、yは順番だけ考えて、tree[0] = [[2, 4], [1]]となります。次に2か4がxのものを探して、それが3番目でtree[2] = [ [3] ]とします。そうして、最初から順番に木を辿ると、2 4 3 1となります。

// Sort Arrays
#![allow(non_snake_case)]

use std::collections::HashMap;


//////////////////// 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()
}


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

type Pair = (usize, i32);

fn read_pair() -> Pair {
    let v: Vec<usize> = read_vec();
    let x = v[0];
    let y = v[1] as i32;
    (x, y)
}

fn read_input() -> Vec<Pair> {
    let N: usize = read();
    (0..N).map(|_| read_pair()).collect::<Vec<Pair>>()
}

fn collect_y(pairs: &Vec<Pair>) -> Vec<Vec<Pair>> {
    let N = pairs.len();
    let mut v: Vec<Vec<Pair>> = vec![vec![]; N+1];
    for (i, &(x, y)) in pairs.iter().enumerate() {
        v[x].push((i+1, y))
    }
    v
}

type Tree = Vec<Vec<Vec<usize>>>;

fn make_tree(pairs: &Vec<Pair>) -> Tree {
    let v = collect_y(pairs);
    let N = pairs.len();
    let mut tree: Tree = vec![vec![]; N+1];
    let mut prevs: Vec<Vec<usize>> = vec![vec![0]];
    while !prevs.is_empty() {
        let mut new_prevs: Vec<Vec<usize>> = vec![];
        for prev in prevs {
            let mut dic: HashMap<i32, Vec<usize>> = HashMap::new();
            let p0 = prev[0];
            for p in prev {
                for &(i, y) in v[p].iter() {
                    let e = dic.entry(y).or_insert(vec![]);
                    (*e).push(i)
                }
            }
            let mut w: Vec<(i32, Vec<usize>)> = dic.into_iter().collect();
            w.sort();
            for (_, mut inds) in w {
                inds.sort();
                tree[p0].push(inds)
            }
            new_prevs.extend(tree[p0].clone())
        }
        prevs = new_prevs
    }
    tree
}

fn sort_indices(i: usize, table: &Tree, v: &mut Vec<usize>) {
    for inds in table[i].iter() {
        v.extend(inds);
        sort_indices(inds[0], table, v)
    }
}

fn F(pairs: Vec<Pair>) {
    let tree = make_tree(&pairs);
    let mut v: Vec<usize> = vec![];
    sort_indices(0, &tree, &mut v);
    println!("{}", v.into_iter().map(|i| i.to_string()).
                                collect::<Vec<String>>().join(" "))
}

fn main() {
    let pairs = read_input();
    F(pairs)
}