use std::cmp::Ordering; use segment_tree::SegmentTree; #[allow(unused_macros)] macro_rules! input { ( $($t:ty),* ) => {{ let mut s = String::new(); std::io::stdin().read_line(&mut s); let mut splits = s.trim().split_whitespace(); ($( { splits.next().unwrap().parse::<$t>().unwrap() },)*) }} } fn dfs(i: usize, weight: u64, edges: &Vec>, mut dist: Vec>) -> Vec> { for (to, w) in &edges[i] { let total_weight = w + weight; if let Some(_) = dist[*to] { continue; } dist[*to] = Some(total_weight); dist = dfs(*to, total_weight, edges, dist); } return dist; } fn euler_tour(i: usize, depth: u32, edges: &Vec>, mut log: Vec, mut visited: Vec>) -> (Vec>, Vec) { visited[i] = Some(log.len()); log.push(Log(i, depth)); for (to, _) in &edges[i] { if let Some(_) = visited[*to] { continue; } let res = euler_tour(*to, depth + 1, edges, log, visited); visited = res.0; log = res.1; log.push(Log(i, depth)); } return (visited, log); } #[allow(dead_code)] mod segment_tree { pub enum SegmentTree { Leaf(T), Node(T, usize, Box>, Box>), } impl SegmentTree { pub fn query(&self, from: usize, to: usize, n: usize) -> (T, usize) { match self { SegmentTree::Leaf(v) => (*v, 0), SegmentTree::Node(v, index, left, right) => { // println!("l = {}, r = {}, n = {}", from, to, n); if to - from + 1 == n { return (*v, *index); } let boundary = n / 2; if from < boundary && boundary <= to { let right_to = to - boundary; // println!(" before go left"); let (lval, lindex) = left.as_ref().query(from, boundary - 1, boundary); // println!(" before go right"); let (rval, rindex) = right.as_ref().query(0, right_to, n - boundary); let rindex = rindex + boundary; if lval < rval { return (lval, lindex); } else { return (rval, rindex); } } if from < boundary { // println!(" before go only left"); return left.as_ref().query(from, to, boundary); } else { let right_from = from - boundary; let right_to = to - boundary; // println!(" before go right"); let (rval, rindex) = right.as_ref().query(right_from, right_to, n - boundary); return (rval, rindex + boundary); } } } } pub fn new(a: &[T], n: usize) -> SegmentTree { if n == 1 { SegmentTree::Leaf(a[0]) } else { let half = n / 2; let left = SegmentTree::new(&a[0..half], half); let right = SegmentTree::new(&a[half..n], n - half); let (i, val) = if left.val() <= right.val() { (left.ind(), left.val()) } else { (right.ind() + half, right.val()) }; SegmentTree::Node(val, i, Box::new(left), Box::new(right)) } } fn val(&self) -> T { match *self { SegmentTree::Node(v, _, _, _) => v, SegmentTree::Leaf(v) => v, } } fn ind(&self) -> usize { match *self { SegmentTree::Node(_, i, _, _) => i, SegmentTree::Leaf(_) => 0, } } } } #[derive(Clone, Copy, Eq)] struct Log(usize, u32); impl Ord for Log { fn cmp(&self, other: &Self) -> Ordering { self.1.cmp(&other.1) } } impl PartialOrd for Log { fn partial_cmp(&self, other: &Self) -> Option { Some(self.cmp(other)) } } impl PartialEq for Log { fn eq(&self, other: &Self) -> bool { self.1 == other.1 } } fn calc_dist(a: usize, b: usize, dist: &Vec, visited: &Vec, tree: &SegmentTree, loglen: usize) -> u64 { let x = std::cmp::min(a, b); let y = std::cmp::max(a, b); let xi = std::cmp::min(visited[x], visited[y]); let yi = std::cmp::max(visited[x], visited[y]); let (Log(lca, _), _) = tree.query(xi, yi + 1, loglen); let xy_dist = dist[x] + dist[y] - 2 * dist[lca]; return xy_dist; } #[allow(unused_must_use)] #[allow(unused_variables)] fn solve() { let (n, ) = input!(usize); let mut edges = vec![vec![]; n]; let mut dist_from_root = vec![None; n]; let mut log = vec![]; let mut visited = vec![None; n]; for _ in 0..(n-1) { let (u, v, w) = input!(usize, usize, u64); edges[u].push((v, w)); edges[v].push((u, w)); } dist_from_root[0] = Some(0); dist_from_root = dfs(0, 0, &edges, dist_from_root); let (visited, log) = euler_tour(0, 0, &edges, log, visited); let loglen = log.len(); let tree = SegmentTree::new(&log[..], loglen); let first_visit: Vec = visited.iter().map(|i| i.unwrap()).collect(); let dist: Vec = dist_from_root.iter().map(|i| i.unwrap()).collect(); let (q, ) = input!(usize); for _ in 0..q { let (x, y, z) = input!(usize, usize, usize); let xy_dist = calc_dist(x, y, &dist, &first_visit, &tree, loglen); let yz_dist = calc_dist(y, z, &dist, &first_visit, &tree, loglen); let zx_dist = calc_dist(z, x, &dist, &first_visit, &tree, loglen); println!("{}", (xy_dist + yz_dist + zx_dist) / 2); } } fn main() { solve(); }