use std::io::*; use std::str::FromStr; struct LCA{ depth:Vec, dig:i32, cost:Vec>, costs:Vec, n:usize, g:Vec>, doubling:Vec> } impl LCA{ fn new(_n:usize) -> Self{ let mut dep:Vec = vec![0;_n]; let mut c:Vec = vec![0;_n]; let mut C:Vec> = vec![vec![];_n]; let mut _g:Vec> = vec![vec![];_n]; let mut digit:usize = 64; let mut doub:Vec> = vec![vec![-1;_n];digit]; LCA{ depth:dep, costs:c, cost:C, doubling:doub, n:_n, dig:digit as i32, g:_g } } fn addedge(&mut self,u:usize,v:usize,c:i32){//コスト指定がなければc = 0を渡す self.g[u].push(v as i32); self.g[v].push(u as i32); self.cost[u].push(c); self.cost[v].push(c); } fn dfs(&mut self,now:usize,par:i32,d:i32,c:i32){ self.doubling[0][now] = par; self.depth[now] = d; self.costs[now] = c; for i in 0..self.g[now].len(){ if self.g[now][i] != par { self.dfs(self.g[now][i] as usize,now as i32,d + 1, c + self.cost[now][i]); } } } fn construct(&mut self){ self.dfs(0,-1,0,0); for i in 0..(self.dig as usize - 1){ for j in 0..self.doubling[i].len(){ if self.doubling[i][j] == -1{ self.doubling[i + 1][j] = -1; } else { self.doubling[i + 1][j] = self.doubling[i][self.doubling[i][j] as usize]; } } } } fn answer_to_query(&mut self, mut u:usize,mut v:usize) -> i32{ if self.depth[u] > self.depth[v] { std::mem::swap(&mut u,&mut v); } for i in (0..self.dig as usize).rev(){ if ((self.depth[v] - self.depth[u]) >> i) & 1 == 0{ v = self.doubling[i][v] as usize; } } if u == v { return u as i32; } for i in (0..self.dig as usize).rev(){ if self.doubling[i][u] != self.doubling[i][v]{ u = self.doubling[i][u] as usize; v = self.doubling[i][v] as usize; } } self.doubling[0][u] } fn length(&mut self,u:usize,v:usize) -> i32 { let mut f = self.answer_to_query(u,v) as usize; self.depth[u] + self.depth[v] - 2 * self.depth[f] } fn dist(&mut self, u:usize,v:usize)-> i32 { let mut f = self.answer_to_query(u,v) as usize; self.costs[u] + self.costs[v] - 2 * self.costs[f] } fn is_on_path(&mut self,u:usize,v:usize,x:usize) -> bool { self.length(u,x) + self.length(v,x) == self.length(u,v) } } fn read() -> T { let stdin = stdin(); let stdin = stdin.lock(); let token: String = stdin .bytes() .map(|c| c.expect("failed to read char") as char) .skip_while(|c| c.is_whitespace()) .take_while(|c| !c.is_whitespace()) .collect(); token.parse().ok().expect("failed to parse token") } fn main(){ let n:usize = read(); let mut abc:Vec> = vec![vec![0;3];n]; let mut lca = LCA::new(n); for i in 0..n - 1{ abc[i] = (0..3).map(|_| read()).collect(); lca.addedge(abc[i][0] as usize - 1, abc[i][1] as usize - 1, abc[i][2]); } lca.construct(); let q:usize = read(); let mut _q:Vec> = vec![vec![0;2];q]; for i in 0..q{ _q[i] = (0..2).map(|_| read()).collect(); } for i in 0..q{ println!("{}",lca.dist(_q[i][0] - 1,_q[i][1] - 1)); } }