use std::{mem::swap, collections::VecDeque}; const INF: usize = 1usize << 60; struct LCA { root: usize, paths: Vec>, parents: Vec>, dists: Vec, lens: Vec, } impl LCA { fn new(root: usize, paths: &Vec>) -> LCA { let mut temp = LCA { root, paths: paths.clone().to_owned(), parents: vec![], dists: vec![], lens: vec![] }; temp._build(); temp } fn _build(&mut self) { let n = self.paths.len(); let mut k = 1usize; while (1usize << k) < n { k += 1; } self.parents = vec![vec![n; n]; k]; self.dists = vec![INF; n]; self.lens = vec![INF; n]; self._dfs(self.root, self.root, 0, 0); for i in 0..k-1 { for j in 0..n { if self.parents[i][j] == self.root { self.parents[i + 1][j] = self.root; } else { self.parents[i + 1][j] = self.parents[i][self.parents[i][j]]; } } } } fn _dfs(&mut self, v: usize, u: usize, dist: usize, len: usize) { self.parents[0][v] = u; self.dists[v] = dist; self.lens[v] = len; for i in 0..self.paths[v].len() { let (vv, cost) = self.paths[v][i]; if vv != u { self._dfs(vv, v, dist + cost, len + 1); } } } fn ancester(&self, left: usize, right: usize) -> usize { let mut l = left; let mut r = right; if self.lens[l] < self.lens[r] { swap(&mut l, &mut r); } let lim = self.parents.len(); for i in 0..lim { if (((self.lens[l] - self.lens[r]) >> i) & 1) == 1 { l = self.parents[i][l]; } } if l == r { return l; } for i in (0..lim).rev() { if self.parents[i][l] != self.parents[i][r] { l = self.parents[i][l]; r = self.parents[i][r]; } } self.parents[0][l] } // 距離の設定がある場合 fn get_dist(&self, left: usize, right: usize) -> usize { self.dists[left] + self.dists[right] - 2 * self.dists[self.ancester(left, right)] } // コスト1の場合 = 辺の本数 fn get_len(&self, left: usize, right: usize) -> usize { self.lens[left] + self.lens[right] - 2 * self.lens[self.ancester(left, right)] } fn on_path(&self, target: usize, left: usize, right: usize) -> bool { self.get_len(target, left) + self.get_len(target, right) == self.get_len(left, right) } } fn main() { let mut n = String::new(); std::io::stdin().read_line(&mut n).ok(); let n: usize = n.trim().parse().unwrap(); let mut paths = vec![vec![]; n]; for _ in 0..n-1 { let mut temp = String::new(); std::io::stdin().read_line(&mut temp).ok(); let temp: Vec = temp.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let u = temp[0]; let v = temp[1]; let w = temp[2]; paths[u].push((v, w)); paths[v].push((u, w)); } let mut q = String::new(); std::io::stdin().read_line(&mut q).ok(); let q: usize = q.trim().parse().unwrap(); let queries = (0..q).map(|_| { let mut temp = String::new(); std::io::stdin().read_line(&mut temp).ok(); let temp: Vec = temp.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); (temp[0], temp[1], temp[2]) }) .collect::>(); let lca = LCA::new(0, &paths); let mut dists = vec![INF; n]; dists[0] = 0; let mut deque = VecDeque::new(); deque.push_back(0); while let Some(u) = deque.pop_front() { for &(v, w) in paths[u].iter() { if dists[v] != INF { continue; } dists[v] = dists[u] + w; deque.push_back(v); } } for &(x, y, z) in queries.iter() { let mut result = INF; for &(x, y, z) in vec![(x,y,z), (x,z,y), (y,x,z), (y,z,x), (z,x,y), (z,y,x)].iter() { let temproot = lca.ancester(x, y); let mut res = dists[x] + dists[y] - 2 * dists[temproot]; let root = lca.ancester(temproot, z); res += dists[temproot] + dists[z] - 2 * dists[root]; result = result.min(res); } println!("{}", result); } }