use proconio::{input, marker::Usize1}; fn main() { input! { n: usize, a: [i64; n], b: [i64; n], edges: [(Usize1, Usize1); n - 1], } let mut graph = vec![vec![]; n]; for &(u, v) in &edges { graph[u].push(v); graph[v].push(u); } let mut pre_order = vec![]; let mut stack = vec![(0, !0)]; while let Some((v, p)) = stack.pop() { pre_order.push(v); graph[v].retain(|&u| u != p); for &u in &graph[v] { stack.push((u, v)); } } let mut dp = vec![[0; 2]; n]; for &v in pre_order.iter().rev() { dp[v][0] = a[v]; for &u in &graph[v] { dp[v][0] += dp[u][0].max(dp[u][1]); dp[v][1] += dp[u][0].max(dp[u][1] + b[v] + b[u]); } } let ans = dp[0][0].max(dp[0][1]); println!("{ans}"); }