import java.io.PrintWriter import java.util.* import kotlin.math.* data class Edge(val node: Int, val cost: Long) fun PrintWriter.solve() { val n = nextInt() val adj = Array(n) { mutableListOf() } val adj2 = Array(n) { mutableListOf() } for (i in 0 until n - 1) { val v1 = nextInt() - 1 val v2 = nextInt() - 1 val c = nextLong() adj[v1].add(v2) adj[v2].add(v1) adj2[v1].add(Edge(v2, c)) adj2[v2].add(Edge(v1, c)) } val lca = LCA(adj, 0) val depth = LongArray(n) { 0L } val stack = Stack>() stack.push(Triple(0, -1, 0)) while (stack.isNotEmpty()) { val (v, p, c) = stack.pop() if (p != -1) { depth[v] = depth[p] + c } for ((w, d) in adj2[v]) { if (w != p) { stack.push(Triple(w, v, d)) } } } val q = nextInt() for (i in 0 until q) { val s = nextInt() - 1 val t = nextInt() - 1 println(depth[s] + depth[t] - 2 * depth[lca.lca(s, t)]) } } class SegTree(private val n: Int, private val op: (Monoid, Monoid) -> Monoid, private val e: Monoid) { private var d: MutableList private var size = 1 private var log = 0 init { while (size < n) { size *= 2 log++ } d = MutableList(2 * size) { e } } constructor(a: Array, op: (Monoid, Monoid) -> Monoid, e: Monoid) : this(a.count(), op, e) { for (i in 0 until n) { d[size + i] = a[i] } for (i in size - 1 downTo 1) update(i) } operator fun set(p: Int, x: Monoid) { if (p !in 0 until n) { throw IllegalArgumentException() } val p1 = p + size d[p1] = x for (i in 1..log) { update(p1 shr i) } } operator fun get(p: Int): Monoid { if (p !in 0 until n) { throw IllegalArgumentException() } return d[p + size] } fun prod(range: IntRange): Monoid { val l = range.first val r = range.last + 1 if (l !in 0..r || r > n) { throw IllegalArgumentException() } var sml = e var smr = e var l1 = l + size var r1 = r + size while (l1 < r1) { if (l1 and 1 != 0) sml = op(sml, d[l1++]) if (r1 and 1 != 0) smr = op(d[--r1], smr) l1 /= 2 r1 /= 2 } return op(sml, smr) } fun allProd(): Monoid { return d[1] } fun maxRight(l: Int, f: (Monoid) -> Boolean): Int { if (l !in 0..n || !f(e)) { throw IllegalArgumentException() } if (l == n) return n var l1 = l + size var sm = e do { while (l1 % 2 == 0) l1 /= 2 if (!f(op(sm, d[l1]))) { while (l1 < size) { l1 *= 2 if (f(op(sm, d[l1]))) { sm = op(sm, d[l1]) l1++ } } return l1 - size } sm = op(sm, d[l1]) l1++ } while ((l1 and -l1) != l1) return n } fun minLeft(r: Int, f: (Monoid) -> Boolean): Int { if (r !in 0..n || !f(e)) { throw IllegalArgumentException() } if (r == 0) return 0 var r1 = r + size var sm = e do { r1-- while (r1 > 1 && r1 % 2 != 0) r1 /= 2 if (!f(op(d[r1], sm))) { while (r1 < size) { r1 = 2 * r1 + 1 if (f(op(d[r1], sm))) { sm = op(d[r1], sm) r1-- } } return r1 + 1 - size } sm = op(d[r1], sm) } while ((r1 and -r1) != r1) return 0 } private fun update(k: Int) { d[k] = op(d[2 * k], d[2 * k + 1]) } fun joinToString(s: String = ", "): String { return (0 until n).map { this[it] }.joinToString(s) } } class LCA(private val adj: Array>, private val root: Int) { private val n = adj.size private val depth = Array(n) { 0 } private val seg: SegTree> private val tin = Array(n) { 0 } init { val lst = mutableListOf>() fun dfs(v: Int, par: Int, d: Int) { tin[v] = lst.size lst.add(d to v) depth[v] = d for (w in adj[v]) { if (w != par) { dfs(w, v, d + 1) } lst.add(d to v) } } dfs(root, -1, 0) seg = SegTree(lst.toTypedArray(), { x, y -> if (x.first < y.first) x else y }, Int.MAX_VALUE to -1) } fun lca(x: Int, y: Int): Int { val l = min(tin[x], tin[y]) val r = max(tin[x], tin[y]) return seg.prod(l..r).second } fun distance(x: Int, y: Int): Int { return depth[x] + depth[y] - 2 * depth[lca(x, y)] } } fun main() { Thread(null, { val writer = PrintWriter(System.out, false) writer.solve() writer.flush() }, "solve", 1.shl(26)).start() } // region Scanner private var st = StringTokenizer("") private val br = System.`in`.bufferedReader() fun next(): String { while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine()) return st.nextToken() } fun nextInt() = next().toInt() fun nextLong() = next().toLong() fun nextLine() = br.readLine() fun nextDouble() = next().toDouble() // endregion