even_tree.rs

use std::io;
//#[macro_use] extern crate text_io;

#[derive(Clone)]
struct Node {
    children: Vec<usize>
}

impl Node {
    fn new() -> Node {
        Node { children: vec![] }
    }
}

fn read_2() -> (usize, usize) {
    let mut input = String::new();
    io::stdin()
        .read_line(&mut input)
        .expect("failed to read from stdin");


    let mut trimmed = input.trim().split(" ");
    (trimmed.next().unwrap().parse::<usize>().unwrap(),
     trimmed.next().unwrap().parse::<usize>().unwrap())
}


fn main() {

    let (n, m) = read_2();

    let mut vertices: Vec<Option<Node>> = vec![None; n];

    for _ in 0..m {
        let (mut v2, mut v1) = read_2();
        v1 -= 1; v2 -= 1;

        {
            let mut popt = &mut vertices[v1];

            if let &mut Some(ref mut p) = popt {
                p.children.push(v2)
            } else {
                let mut p = Node::new();
                p.children.push(v2);
                *popt = Some(p);
            }
        }

        if vertices[v2].is_none() {
            vertices[v2] = Some(Node::new());
        }
    }

    let vertices: Vec<Node> = vertices.into_iter().map(|v| v.unwrap()).collect();

    let mut used: Vec<bool> = vec![false; n];
    for node in vertices.iter() {
        for &child in node.children.iter() {
            used[child] = true;
        }
    }

    let root = used.into_iter().position(|v| !v).unwrap();

    let (_, rm) = solve(&vertices, root);
    println!("{}", rm);
}


fn solve(vertices: &Vec<Node>, root: usize) -> (usize, usize) {
    let mut rm = 0;
    let mut count = 1;

    for &v in vertices[root].children.iter() {
        let (child_count, child_rm) = solve(vertices, v);
        rm += child_rm;
        if child_count & 1 == 0 {
            rm += 1;
        }
        count += child_count;
    }

    (count, rm)
}