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