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)); } let dist0 = dfs_dist(&graph, 0); let leaf1 = (0 .. n).max_by_key(|&v| dist0[v] ).unwrap(); let dist1 = dfs_dist(&graph, leaf1); let diameter = dist1.into_iter().max().unwrap(); println!("{diameter}"); } const INF: i64 = 1_000_000_000_000_000_000; fn dfs_dist(graph: &[Vec<(usize, i64)>], start: usize) -> Vec { let mut dist = vec![INF; graph.len()]; dist[start] = 0; let mut stack = vec![(start, start)]; while let Some((u, p)) = stack.pop() { for &(v, w) in &graph[u] { if v == p { continue; } dist[v] = dist[u] + w; stack.push((v, u)); } } dist }