#![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::(); let a = read_vec::(); let b = read_vec::(); let mut edges: Vec> = vec![Vec::new(); n]; for _ in 0..n - 1 { let v = read_vec::(); let (a, b) = (v[0] - 1, v[1] - 1); edges[a].push(b); edges[b].push(a); } let mut tree: Vec> = vec![Vec::new(); n]; let mut parent_dict: HashMap = 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::() + a[ti]; dp[ti][1] = tree[ti] .iter() .map(|&ci| max(dp[ci][0], dp[ci][1] + b[ci] + b[ti])) .sum::(); } // debug!(dp[3]); println!("{}", max(dp[0][0], dp[0][1])); } fn read() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } fn read_vec() -> Vec { read::() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } fn make_tree( cur_idx: usize, parent_idx: usize, edges: &Vec>, tree: &mut Vec>, parent_dict: &mut HashMap, ) { 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>, result: &mut Vec) { for child_idx in tree[cur_idx].iter() { result.push(*child_idx); topological_dfs(*child_idx, tree, result); } }