// ---------- begin Lowest Common Ancestor ---------- struct LCA { graph: Vec>, parent: Vec, path_root: Vec, path_parent: Vec, index: Vec } impl LCA { fn new(n: usize) -> Self { LCA { graph: vec![vec![]; n], parent: vec![], path_root: vec![], path_parent: vec![], index: vec![], } } fn add_edge(&mut self, a: usize, b: usize) { assert!(a != b && a < self.graph.len() && b < self.graph.len()); self.graph[a].push(b); self.graph[b].push(a); } fn build(&mut self, root: usize) { let n = self.graph.len(); assert!(root < n); let mut parent = vec![root; n]; let mut q = vec![root]; let graph = &mut self.graph; for i in 0..n { let v = q[i]; let p = parent[v]; let child = &mut graph[v]; if let Some(k) = child.iter().position(|u| *u == p) { child.swap_remove(k); } for &u in child.iter() { parent[u] = v; q.push(u); } } let mut size = vec![1; n]; for &v in q.iter().rev() { if graph[v].is_empty() { continue; } let mut max = (0, 0); for (i, &u) in graph[v].iter().enumerate() { size[v] += size[u]; if size[u] > max.0 { max = (size[u], i); } } graph[v].swap(0, max.1); } let mut path_root = vec![root; n]; let mut path_parent = vec![root; n]; let mut index = vec![n; n]; let mut stack = vec![root]; let mut k = 0; while let Some(v) = stack.pop() { index[v] = k; k += 1; if graph[v].is_empty() { continue; } for &u in graph[v].iter().skip(1) { path_root[u] = u; path_parent[u] = v; stack.push(u); } let u = graph[v][0]; path_root[u] = path_root[v]; path_parent[u] = path_parent[v]; stack.push(u); } self.parent = parent; self.path_root = path_root; self.path_parent = path_parent; self.index = index; } fn query(&self, mut a: usize, mut b: usize) -> usize { let path = &self.path_root; let parent = &self.path_parent; let index = &self.index; while path[a] != path[b] { if index[a] < index[b] { b = parent[b]; } else { a = parent[a]; } } if index[a] < index[b] {a} else {b} } fn parent(&self, v: usize) -> Option { let p = self.parent[v]; if p == v { None } else { Some(p) } } } // ---------- end Lowest Common Ancestor ---------- // ---------- begin chmin, chmax ---------- pub trait ChangeMinMax { fn chmin(&mut self, x: Self) -> bool; fn chmax(&mut self, x: Self) -> bool; } impl ChangeMinMax for T { fn chmin(&mut self, x: Self) -> bool { *self > x && { *self = x; true } } fn chmax(&mut self, x: Self) -> bool { *self < x && { *self = x; true } } } // ---------- end chmin, chmax ---------- // ---------- begin scannner ---------- #[allow(dead_code)] mod scanner { use std::str::FromStr; pub struct Scanner<'a> { it: std::str::SplitWhitespace<'a>, } impl<'a> Scanner<'a> { pub fn new(s: &'a String) -> Scanner<'a> { Scanner { it: s.split_whitespace(), } } pub fn next(&mut self) -> T { self.it.next().unwrap().parse::().ok().unwrap() } pub fn next_bytes(&mut self) -> Vec { self.it.next().unwrap().bytes().collect() } pub fn next_chars(&mut self) -> Vec { self.it.next().unwrap().chars().collect() } pub fn next_vec(&mut self, len: usize) -> Vec { (0..len).map(|_| self.next()).collect() } } } // ---------- end scannner ---------- use std::io::Write; fn main() { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); let mut sc = scanner::Scanner::new(&s); let out = std::io::stdout(); let mut out = std::io::BufWriter::new(out.lock()); run(&mut sc, &mut out); } fn run(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter) { let n: usize = sc.next(); let k: usize = sc.next(); let mut g = vec![vec![]; n]; let mut lca = LCA::new(n); for _ in 1..n { let a = sc.next::() - 1; let b = sc.next::() - 1; let c = sc.next::(); lca.add_edge(a, b); g[a].push((b, c)); g[b].push((a, c)); } let root = n - 1; lca.build(root); let inf = std::u64::MAX / 10; let mut depth = vec![inf; n]; depth[root] = 0; let mut dfs = vec![root]; while let Some(v) = dfs.pop() { let d = depth[v]; for &(u, c) in g[v].iter() { if depth[u].chmin(d + c) { dfs.push(u); } } } let dijkstra = |src: &[usize]| -> Vec { let mut dp = vec![inf; n]; let mut h = std::collections::BinaryHeap::new(); use std::cmp::*; for &v in src.iter() { dp[v] = 0; h.push(Reverse((0, v))); } while let Some(Reverse((d, v))) = h.pop() { if d > dp[v] { continue; } for &(u, w) in g[v].iter() { if dp[u].chmin(d + w) { h.push(Reverse((dp[u], u))); } } } dp }; let mut memo = vec![]; for _ in 0..k { let m: usize = sc.next(); let p: u64 = sc.next(); let mut x = vec![0usize; m]; for x in x.iter_mut() { *x = sc.next::() - 1; } memo.push((p, dijkstra(&x))); } let mut g = vec![vec![inf; 2 * k]; 2 * k]; for (i, a) in memo.iter().enumerate() { g[i][i] = 0; g[i][i + k] = a.0; g[i + k][i + k] = 0; for (j, b) in memo.iter().enumerate().take(i) { let d = a.1.iter().zip(b.1.iter()).map(|p| *p.0 + *p.1).min().unwrap(); g[i + k][j] = d; g[j + k][i] = d; } } for x in 0..(2 * k) { for i in 0..(2 * k) { for j in 0..(2 * k) { let d = g[i][x] + g[x][j]; g[i][j].chmin(d); } } } let q: usize = sc.next(); for _ in 0..q { let s = sc.next::() - 1; let t = sc.next::() - 1; let mut ans = depth[s] + depth[t] - 2 * depth[lca.query(s, t)]; for (i, a) in memo.iter().enumerate() { ans.chmin(a.1[s] + a.0 + a.1[t]); for (j, b) in memo.iter().enumerate() { ans.chmin(a.1[s] + g[i][j + k] + b.1[t]); } } writeln!(out, "{}", ans).ok(); } }