#![allow( dead_code, non_snake_case, unused_imports, unused_mut, unused_variables, while_true, unused_assignments, clippy::needless_range_loop, clippy::ptr_arg, clippy::type_complexity, clippy::unnecessary_cast )] use proconio::{ input, marker::{Chars, Usize1 as usize1}, }; use std::collections::{BinaryHeap, HashMap, HashSet, VecDeque}; type Memo = HashMap, i64>>; fn dfs(v: usize, p: Option, g: &Vec>, memo: &mut Memo) -> i64 { if let Some(m) = memo.get(&v) { if let Some(m) = m.get(&p) { return *m; } } let mut max = 0; for &(u, w) in g[v].iter() { if Some(u) == p { continue; } let d = dfs(u, Some(v), g, memo); max = max.max(d + w); } memo.entry(v).or_default().insert(p, max); max } fn main() { input! { N: usize, uvw: [(usize1, usize1, i64); N-1], }; let mut g = vec![vec![]; N]; for &(u, v, w) in uvw.iter() { g[u].push((v, w)); g[v].push((u, w)); } let mut memo = Memo::new(); let mut max = 0; for i in 0..N { let d = dfs(i, None, &g, &mut memo); max = max.max(d); } println!("{}", max); }