CSA #60 E問題

Rust で書き直したのだが Rust で提出できなかった。そういえばクロージャ再帰ってできるんだろうか。グラフを引数に渡すのくどい。

パスを交差させる必要はなくて、互いに素なものだけ考慮すれば良い。これは適当な木DPで解ける――具体的には、状態を(dp0: 親と繋がない)(dp1:親と繋ぐ)として値を (パス数, パス長) とすれば良い。

macro_rules! input {
  ($($x:ident : $t:ty), *) => {
    $(let $x: $t;)*
    {
      let mut s = String::new();
      std::io::stdin().read_line(&mut s).unwrap();
      let mut it = s.trim().split_whitespace();
      $($x = it.next().unwrap().parse().unwrap();)*
      assert!(it.next().is_none());
    }
  };
}

fn dfs(u: usize, p: usize, g: &Vec<Vec<(usize, i32)>>) -> ((i32, i32), (i32, i32)) {
  use std::cmp;

  let mut dp0 = (0, 0);
  let mut dp1 = (1, 0);

  for &(v, c) in &g[u] {
    if v == p { continue }
    let (ep0, ep1) = dfs(v, u, g);

    let x0 = (dp0.0 + ep0.0    , dp0.1 + ep0.1);
    let y0 = (dp1.0 + ep0.0    , dp1.1 + ep0.1);
    let x1 = (dp1.0 + ep1.0 - 1, dp1.1 + ep1.1 + 1);
    let y1 = (dp0.0 + ep1.0    , dp0.1 + ep1.1 + 1);

    if c == 0 {
      dp0 = x0;
      dp1 = y0;
    } else if c == 1 {
      dp0 = x1;
      dp1 = y1;
    } else {
      dp0 = cmp::min(x0, x1);
      dp1 = cmp::min(y0, y1);
    }
  }
  (dp0, dp1)
}

fn main() {
  input!(n: usize);

  let mut g: Vec<Vec<(usize, i32)>> = vec![Vec::new(); n];

  for _ in 1..n {
    input!(a: usize, b: usize, c: i32, d: i32);
    let a = a - 1;
    let b = b - 1;
    let d = if d != 2 { c ^ d } else { d };
    g[a].push((b, d));
    g[b].push((a, d));
  }

  let ((x, y), _) = dfs(0, n, &g);
  println!("{} {}", x, y);
}