use proconio::{input, marker::Usize1}; fn main() { input! { n: usize, edges: [(Usize1, Usize1, i64); n - 1], } let mut graph = vec![vec![]; n]; for &(u, v, w) in &edges { graph[u].push((v, w)); graph[v].push((u, w)); } fn dfs(graph: &[Vec<(usize, i64)>], u: usize, p: usize, down: i64, ans: &mut i64) -> i64 { *ans = down.max(*ans); let mut up = 0; for &(v, w) in &graph[u] { if v == p { continue; } let child_down = down.max(up) + w; let child_up = dfs(graph, v, u, child_down, ans); up = up.max(child_up + w); } up } let mut ans = 0; for _ in 0 .. 2 { dfs(&graph, 0, 0, 0, &mut ans); for v in 0 .. n { graph[v].reverse(); } } println!("{ans}"); }