結果
問題 | No.1221 木 *= 3 |
ユーザー |
![]() |
提出日時 | 2020-09-04 22:07:26 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 126 ms / 2,000 ms |
コード長 | 2,436 bytes |
コンパイル時間 | 12,692 ms |
コンパイル使用メモリ | 407,468 KB |
実行使用メモリ | 34,072 KB |
最終ジャッジ日時 | 2024-11-26 12:57:21 |
合計ジャッジ時間 | 15,561 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 18 |
ソースコード
#![allow(unused_imports)] #![allow(non_snake_case)] use std::cmp::*; use std::collections::*; use std::io::Write; #[allow(unused_macros)] macro_rules! debug { ($($e:expr),*) => { #[cfg(debug_assertions)] $({ let (e, mut err) = (stringify!($e), std::io::stderr()); writeln!(err, "{} = {:?}", e, $e).unwrap() })* }; } fn main() { let n = read::<usize>(); let a = read_vec::<i64>(); let b = read_vec::<i64>(); let mut edges: Vec<Vec<usize>> = vec![Vec::new(); n]; for _ in 0..n - 1 { let v = read_vec::<usize>(); let (a, b) = (v[0] - 1, v[1] - 1); edges[a].push(b); edges[b].push(a); } let mut tree: Vec<Vec<usize>> = vec![Vec::new(); n]; let mut parent_dict: HashMap<usize, usize> = HashMap::new(); make_tree(0, n, &edges, &mut tree, &mut parent_dict); let mut topological_sorted_indexes = vec![0]; topological_dfs(0, &tree, &mut topological_sorted_indexes); let mut dp = vec![vec![0; 2]; n]; for &ti in topological_sorted_indexes.iter().rev() { dp[ti][0] = tree[ti] .iter() .map(|&ci| max(dp[ci][0], dp[ci][1])) .sum::<i64>() + a[ti]; dp[ti][1] = tree[ti] .iter() .map(|&ci| max(dp[ci][0], dp[ci][1] + b[ci] + b[ti])) .sum::<i64>(); } // debug!(dp[3]); println!("{}", max(dp[0][0], dp[0][1])); } fn read<T: std::str::FromStr>() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } fn read_vec<T: std::str::FromStr>() -> Vec<T> { read::<String>() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } fn make_tree( cur_idx: usize, parent_idx: usize, edges: &Vec<Vec<usize>>, tree: &mut Vec<Vec<usize>>, parent_dict: &mut HashMap<usize, usize>, ) { for child_idx in edges[cur_idx].iter() { if *child_idx == parent_idx { continue; } tree[cur_idx].push(*child_idx); parent_dict.insert(*child_idx, cur_idx); make_tree(*child_idx, cur_idx, edges, tree, parent_dict); } } fn topological_dfs(cur_idx: usize, tree: &Vec<Vec<usize>>, result: &mut Vec<usize>) { for child_idx in tree[cur_idx].iter() { result.push(*child_idx); topological_dfs(*child_idx, tree, result); } }