AtCoder Beginner Contest 270 C

https://atcoder.jp/contests/abc270/tasks/abc270_c

各点のXからの距離を調べて、Yからトレースバックします。
Yにたどり着いたら距離を調べるのを打ち切ってもいいのですが、これでも十分速いです。

// Simple path
#![allow(non_snake_case)]

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

type Graph = Vec<Vec<usize>>;

fn read_input() -> (usize, usize, Graph) {
    let v: Vec<usize> = read_vec();
    let N = v[0];
    let X = v[1] - 1;
    let Y = v[2] - 1;
    let mut g: Graph = (0..N).map(|_| Vec::<usize>::new()).collect();
    for _ in 0..(N-1) {
        
        let w: Vec<usize> = read_vec();
        let U = w[0] - 1;
        let V = w[1] - 1;
        g[U].push(V);
        g[V].push(U);
    }
    (X, Y, g)
}

fn create_distance_vector(graph: &Graph, X: usize) -> Vec<i32> {
    let N = graph.len();
    let mut dists: Vec<i32> = (0..N).map(|_| -1).collect();
    dists[X] = 0;
    let mut stack: Vec<usize> = vec![X];
    while !stack.is_empty() {
        let v0 = stack.pop().unwrap();
        for ref_v1 in graph[v0].iter() {
            let v1 = *ref_v1;
            if dists[v1] == -1 {
                dists[v1] = dists[v0] + 1;
                stack.push(v1)
            }
        }
    }
    dists
}

fn trace_back(X: usize, Y: usize, dists: Vec<i32>, graph: Graph) -> Vec<usize> {
    let mut rev_path = Vec::<usize>::new();
    let mut v0 = Y;
    rev_path.push(v0);
    while v0 != X {
        for ref_v1 in graph[v0].iter() {
            let v1 = *ref_v1;
            if dists[v1] == dists[v0] - 1 {
                rev_path.push(v1);
                v0 = v1;
                break
            }
        }
    }
    rev_path
}

fn f(X: usize, Y: usize, graph: Graph) -> Vec<usize> {
    let dists = create_distance_vector(&graph, X);
    let rev_path = trace_back(X, Y, dists, graph);
    return rev_path.iter().map(|n| n+1).rev().collect();
}

fn main() {
    let v = read_input();
    let path = f(v.0, v.1, v.2);
    let str_path: Vec<String> = path.iter().map(|&i| i.to_string()).collect();
    println!("{}", str_path.join(" "))
}