#![allow(unused_imports)] #![allow(dead_code)] #![allow(non_camel_case_types)] #![allow(non_snake_case)] use std::cmp::*; use std::collections::*; use std::ops::*; use std::io::{Write, BufWriter}; const MOD: usize = 998244353; // https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 macro_rules! input { ($($r:tt)*) => { let stdin = std::io::stdin(); let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next = move || -> String{ bytes .by_ref() .map(|r|r.unwrap() as char) .skip_while(|c|c.is_whitespace()) .take_while(|c|!c.is_whitespace()) .collect() }; input_inner!{next, $($r)*} }; } macro_rules! input_inner { ($next:expr) => {}; ($next:expr, ) => {}; ($next:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($next, $t); input_inner!{$next $($r)*} }; } macro_rules! read_value { ($next:expr, ( $($t:tt),* )) => { ( $(read_value!($next, $t)),* ) }; ($next:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($next, $t)).collect::>() }; ($next:expr, chars) => { read_value!($next, String).chars().collect::>() }; ($next:expr, usize1) => { read_value!($next, usize) - 1 }; ($next:expr, [ $t:tt ]) => {{ let len = read_value!($next, usize); (0..len).map(|_| read_value!($next, $t)).collect::>() }}; ($next:expr, $t:ty) => { $next().parse::<$t>().expect("Parse error") }; } #[derive(Copy,Clone)] struct Pair { x: T, y: U, } impl Pair { fn new(x: T, y: U) -> Pair { Pair { x: x, y: y, } } } struct euler_tour { G: Vec>>, tour: Vec, L: Vec, R: Vec, depth: Vec, weight: Vec, n: usize, } impl euler_tour{ fn new(n: usize) -> euler_tour { euler_tour{ G: vec![vec![];n], tour: vec![], L: vec![0;n], R: vec![0;n], depth: vec![0;n], weight: vec![0;n], n: n, } } fn add_edge(&mut self, s: usize, t: usize, w: i64){ self.G[s].push(Pair::new(t,w)); self.G[t].push(Pair::new(s,w)); } fn start_tour(&mut self, root: usize) { self.dfs(root, self.n, 0, 0); } fn dfs(&mut self, v: usize, p: usize, d: usize, w: i64){ self.tour.push(v); self.L[v] = self.tour.len()-1; self.depth[v] = d; self.weight[v] = w; for z in self.G[v].clone() { if z.x == p {continue;} self.dfs(z.x, v, d+1, w+z.y); self.tour.push(v); } self.R[v] = self.tour.len()-1; } } struct sparse_table { log_t: Vec, table: Vec>>, n: usize, } impl sparse_table { fn new(arr: Vec>) -> sparse_table { let n = arr.len(); let mut lt: Vec = vec![0;n+1]; for i in 2..n+1 { lt[i] = lt[i >> 1] + 1; } let sz = lt[n]; let mut st = sparse_table { log_t: lt, table: vec![vec![Pair::new(usize::max_value(),0);sz+1];n], n: n, }; for i in 0..n { st.table[i][0] = arr[i]; } for k in 1..n { if (1 << k) > n {break;} for i in 0..n { if i + (1 << k) > n {break;} st.table[i][k] = { let a = st.table[i][k - 1]; let b = st.table[i + (1 << (k - 1))][k - 1]; if a.x <= b.x {a} else {b} }; } } st } fn query(&mut self, s: usize, t: usize) -> Pair { let k = self.log_t[t-s+1]; let a = self.table[s][k]; let b = self.table[t + 1 - (1 << k)][k]; if a.x <= b.x {a} else {b} } } fn dist(x: usize, y: usize, euler: &euler_tour, st: &mut sparse_table) -> i64 { let c = st.query(min(euler.L[x],euler.L[y]), max(euler.R[x], euler.R[y])).y; euler.weight[x] + euler.weight[y] - 2*euler.weight[c] } fn solve() { input! { n: usize, a: [[usize;3];n-1], q: usize, b: [[usize;3];q], } let mut euler = euler_tour::new(n); for i in 0..n-1{ euler.add_edge(a[i][0], a[i][1], a[i][2] as i64); } euler.start_tour(0); let sz = euler.tour.len(); let mut arr: Vec> = vec![Pair::new(0,0);sz]; for i in 0..sz { arr[i] = Pair::new(euler.depth[euler.tour[i]], euler.tour[i]); } let mut st = sparse_table::new(arr); for i in 0..q { let x = b[i][0]; let y = b[i][1]; let z = b[i][2]; let ans = dist(x,y,&euler,&mut st) + dist(y,z,&euler,&mut st) + dist(x,z,&euler,&mut st); println!("{}", ans/2); } } fn main() { // In order to avoid potential stack overflow, spawn a new thread. let stack_size = 104_857_600; // 100 MB let thd = std::thread::Builder::new().stack_size(stack_size); thd.spawn(|| solve()).unwrap().join().unwrap(); }