AtCoder Beginner Contest 333 D

https://atcoder.jp/contests/abc333/tasks/abc333_d

1を含むエッジを除いてUnion-Findを構築します。そうしたとき、一番点の数の大きな木以外を足すと求める値になります。

// Erase Leaves
#![allow(non_snake_case)]

use std::cmp::max;


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


//////////////////// UnionFind ////////////////////

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

struct UnionFind {
    parents: Vec<Node>,
    heights: Vec<i32>,
}

impl UnionFind {
    fn new(N: usize) -> UnionFind {
        let parents: Vec<Node> = (0..N).collect();
        let heights: Vec<i32> = vec![1; N];
        UnionFind { parents, heights }
    }
    
    fn is_root(&self, v: Node) -> bool {
        self.parents[v] == v
    }
    
    fn join(&mut self, edge: &Edge) {
        let r1 = self.root(edge.0);
        let r2 = self.root(edge.1);
        if r1 == r2 {
            return  // ここには来ないはず
        }
        
        let h1 = self.heights[r1];
        let h2 = self.heights[r2];
        if h1 <= h2 {   // r2にr1がぶら下がる
            self.parents[r1] = r2;
            self.heights[r2] = max(self.heights[r2], self.heights[r1]+1);
        }
        else {
            self.parents[r2] = r1;
            self.heights[r1] = max(self.heights[r1], self.heights[r2]+1);
        }
    }
    
    fn root(&self, v0: Node) -> Node {
        if self.is_root(v0) {
            v0
        }
        else {
            let p = self.parents[v0];
            self.root(p)
        }
    }
}


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

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

fn F(edges: Vec<Edge>) -> usize {
    let N = edges.len() + 1;
    let mut tree = UnionFind::new(N);
    for (u, v) in edges.into_iter() {
        if u != 0 && v != 0 {
            tree.join(&(u, v))
        }
    }
    
    let mut parents: Vec<usize> = vec![0; N];
    for v in 0..N {
        parents[tree.root(v)] += 1
    }
    N - parents.iter().map(|&n| n).max().unwrap()
}

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