AtCoder Beginner Contest 361 E

https://atcoder.jp/contests/abc361/tasks/abc361_e

端点から端点に移動するとき、横道は2回エッジを通りますがそうでない経路は1回しか通らないので、木の直径を求めればよいです。

// Tree and Hamilton Path 2
#![allow(non_snake_case)]


//////////////////// 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 Dist = i64;
type Edge = (Node, Node, Dist);

fn read_edge() -> Edge {
    let v: Vec<usize> = read_vec();
    let (A, B) = (v[0]-1, v[1]-1);
    let C = v[2] as Dist;
    (A, B, C)
}

type Graph = Vec<Vec<(Node, Dist)>>;

fn create_graph(N: usize, edges: Vec<Edge>) -> Graph {
    let mut graph: Graph = vec![vec![]; N];
    for (A, B, C) in edges.into_iter() {
        graph[A].push((B, C));
        graph[B].push((A, C))
    }
    graph
}

fn fathest_point(v0: Node, graph: &Graph) -> (Node, Dist) {
    let N = graph.len();
    let mut visited: Vec<bool> = vec![false; N];
    let mut dists: Vec<Dist> = vec![0; N];
    visited[v0] = true;
    let mut stack: Vec<Node> = vec![v0];
    while let Some(v) = stack.pop() {
        for &(v1, d1) in graph[v].iter() {
            if !visited[v1] {
                visited[v1] = true;
                dists[v1] = dists[v] + d1;
                stack.push(v1)
            }
        }
    }
    let (dmax, vmax) = (0..N).map(|i| (dists[i], i)).max().unwrap();
    (vmax, dmax)
}

fn diameter(graph: &Graph) -> Dist {
    let (v, _) = fathest_point(0, graph);
    let (_, d) = fathest_point(v, graph);
    d
}


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

fn read_input() -> Vec<Edge> {
    let N: usize = read();
    let edges: Vec<Edge> = (0..N-1).map(|_| read_edge()).collect();
    edges
}

fn F(edges: Vec<Edge>) -> Dist {
    let all_edge_dist = edges.iter().map(|&(_, _, d)| d).sum::<Dist>();
    let N = edges.len() + 1;
    let graph = create_graph(N, edges);
    let d = diameter(&graph);
    all_edge_dist * 2 - d
}

fn main() {
    let edges = read_input();
    println!("{}", F(edges))
}