結果
問題 | 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);}}