//---------- begin SegmentTree Point update Range query ---------- mod segment_tree { pub struct PURQ T> { n: usize, a: Vec, id: T, op: F, } #[allow(dead_code)] impl T> PURQ { pub fn new(n: usize, id: T, op: F) -> PURQ { let mut k = 1; while k < n { k *= 2; } PURQ { n: k, a: vec![id.clone(); 2 * k], id: id, op: op, } } pub fn update(&mut self, x: usize, v: T) { let mut k = self.n + x; let a = &mut self.a; a[k] = v; k >>= 1; while k > 0 { a[k] = (self.op)(a[2 * k].clone(), a[2 * k + 1].clone()); k >>= 1; } } pub fn update_tmp(&mut self, x: usize, v: T) { self.a[x + self.n] = v; } pub fn update_all(&mut self) { for k in (1..(self.n)).rev() { self.a[k] = (self.op)(self.a[2 * k].clone(), self.a[2 * k + 1].clone()); } } pub fn find(&self, mut l: usize, mut r: usize) -> T { let mut p = self.id.clone(); let mut q = self.id.clone(); l += self.n; r += self.n; while l < r { if (l & 1) == 1 { p = (self.op)(p, self.a[l].clone()); l += 1; } if (r & 1) == 1 { r -= 1; q = (self.op)(self.a[r].clone(), q); } l >>= 1; r >>= 1; } (self.op)(p, q) } } } //---------- end SegmentTree Point update Range query ---------- use std::io::{Read, Write}; use std::cmp::{min, max}; fn dfs(v: usize, d: u64, p: usize, g: &[Vec<(usize, u64)>], l: &mut [usize], r: &mut [usize], ini: &mut Vec<(u64, usize)>) { let k = ini.len(); l[v] = k; ini.push((d, v)); for &(u, w) in &g[v] { if u == p { continue; } dfs(u, d + w, v, g, l, r, ini); ini.push((d, v)); } r[v] = ini.len(); } fn run() { let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); let mut it = s.trim().split_whitespace(); let n: usize = it.next().unwrap().parse().unwrap(); let mut g = vec![vec![]; n]; for _ in 1..n { let u: usize = it.next().unwrap().parse().unwrap(); let v: usize = it.next().unwrap().parse().unwrap(); let w: u64 = it.next().unwrap().parse().unwrap(); g[u].push((v, w)); g[v].push((u, w)); } let mut left = vec![0; n]; let mut right = vec![0; n]; let mut ini = vec![]; dfs(0, 0, 0, &g, &mut left, &mut right, &mut ini); let mut s = segment_tree::PURQ::new(ini.len(), (std::u64::MAX, 0), std::cmp::min); for (i, p) in ini.iter().enumerate() { s.update_tmp(i, *p); } s.update_all(); let q: usize = it.next().unwrap().parse().unwrap(); let out = std::io::stdout(); let mut out = std::io::BufWriter::new(out.lock()); for _ in 0..q { let x: usize = it.next().unwrap().parse().unwrap(); let y: usize = it.next().unwrap().parse().unwrap(); let z: usize = it.next().unwrap().parse().unwrap(); let l = min(min(left[x], left[y]), left[z]); let r = max(max(right[x], right[y]), right[z]); let (root_depth, root) = s.find(l, r); let mut ans = ini[left[x]].0 + ini[left[y]].0 + ini[left[z]].0 - 3 * root_depth; for &(x, y) in [(x, y), (y, z), (z, x)].iter() { let (ud, u) = s.find(min(left[x], left[y]), max(right[x], right[y])); if u != root { ans -= ud - root_depth; } } writeln!(out, "{}", ans).unwrap(); } } fn main() { run(); }