use proconio::input; use std::cmp::Reverse; fn main() { input! { n: usize, edges: [(usize, usize, u64); n - 1], q: usize, queries: [(usize, usize, usize); q], } let mut g = vec![Vec::new(); n]; for &(i, j, _) in &edges { g[i].push(j); g[j].push(i); } let mut stack = vec![0]; let mut parent = vec![usize::MAX; n]; parent[0] = 0; let mut size = vec![1; n]; while let Some(x) = stack.pop() { if x <= isize::MAX as usize { stack.push(!x); g[x].retain(|&y| y != parent[x]); for &y in &g[x] { if parent[y] != usize::MAX { continue; } parent[y] = x; stack.push(y); } } else { let x = !x; g[x].sort_unstable_by_key(|&y| Reverse(size[y])); for &y in &g[x] { size[x] += size[y]; } } } let mut sorted = Vec::new(); let mut position = vec![usize::MAX; n]; let mut head = (0..n).collect::>(); let mut stack = vec![0]; while let Some(x) = stack.pop() { position[x] = sorted.len(); sorted.push(x); if let Some(&y) = g[x].first() { head[y] = head[x]; } stack.extend(g[x].iter().rev().copied()); } let mut values = vec![0; n]; for &(i, j, w) in &edges { let i = if parent[i] == j { i } else { j }; values[position[i]] = w; } for i in (0..n - 1).rev() { values[i] += values[i + 1]; } values.push(0); for &(mut i, mut j, mut k) in &queries { let mut ans = 0; loop { if position[i] > position[j] { std::mem::swap(&mut i, &mut j); } if position[j] > position[k] { std::mem::swap(&mut j, &mut k); } if position[i] > position[j] { std::mem::swap(&mut i, &mut j); } if head[j] == head[k] { ans += values[position[j] + 1] - values[position[k] + 1]; break; } ans += values[position[head[k]]] - values[position[k] + 1]; k = parent[head[k]]; } loop { if position[i] > position[j] { std::mem::swap(&mut i, &mut j); } if head[i] == head[j] { ans += values[position[i] + 1] - values[position[j] + 1]; break; } ans += values[position[head[j]]] - values[position[j] + 1]; j = parent[head[j]]; } println!("{}", ans); } }