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() { match x >> (usize::BITS - 1) & 1 { 0 => { 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); } } 1 => { let x = !x; g[x].sort_unstable_by_key(|&y| Reverse(size[y])); for &y in &g[x] { size[x] += size[y]; } } _ => unreachable!(), } } 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 &(i, j, k) in &queries { let mut ans = 0; for &(mut i, mut j) in &[(i, j), (j, k), (k, i)] { 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]]; } } ans /= 2; println!("{}", ans); } }