use std::cmp::*; macro_rules !input {(source =$s :expr ,$($r :tt ) *) =>{let mut iter =$s .split_whitespace () ;let mut next =||{iter .next () .unwrap () } ;input_inner !{next ,$($r ) *} } ;($($r :tt ) *) =>{let stdin =std ::io ::stdin () ;let mut bytes =std ::io ::Read ::bytes (std ::io ::BufReader ::new (stdin .lock () ) ) ;let mut next =move ||->String {bytes .by_ref () .map (|r |r .unwrap () as char ) .skip_while (|c |c .is_whitespace () ) .take_while (|c |!c .is_whitespace () ) .collect () } ;input_inner !{next ,$($r ) *} } ;} macro_rules !input_inner {($next :expr ) =>{} ;($next :expr ,) =>{} ;($next :expr ,$var :ident :$t :tt $($r :tt ) *) =>{let $var =read_value !($next ,$t ) ;input_inner !{$next $($r ) *} } ;} macro_rules !read_value {($next :expr ,($($t :tt ) ,*) ) =>{($(read_value !($next ,$t ) ) ,*) } ;($next :expr ,[$t :tt ;$len :expr ] ) =>{(0 ..$len ) .map (|_ |read_value !($next ,$t ) ) .collect ::>() } ;($next :expr ,chars ) =>{read_value !($next ,String ) .chars () .collect ::>() } ;($next :expr ,usize1 ) =>{read_value !($next ,usize ) -1 } ;($next :expr ,$t :ty ) =>{$next () .parse ::<$t >() .expect ("Parse error" ) } ;} fn main() { input! { n: usize, a: [i64; n], b: [i64; n], uv: [(usize, usize); n-1] } let mut to = vec![vec![]; n]; for &(u, v) in uv.iter() { to[u - 1].push(v - 1); to[v - 1].push(u - 1); } let mut dp = vec![vec![0; 2]; n]; dfs(0, 0, &to, &a, &b, &mut dp); let ans = max(dp[0][0], dp[0][1]); println!("{}", ans); } fn dfs( u: usize, p: usize, to: &Vec>, a: &Vec, b: &Vec, dp: &mut Vec>, ) { dp[u][0] = a[u]; for &v in to[u].iter() { if v == p { continue; } dfs(v, u, to, a, b, dp); dp[u][0] += max(dp[v][0], dp[v][1]); dp[u][1] += max(dp[v][0], dp[v][1] + b[u] + b[v]); } }