import java.io.*; import java.math.BigDecimal; import java.util.*; @SuppressWarnings("unused") public class Main { FastScanner in; PrintWriter out; final static int MOD = (int)1e9+7; void solve(){ int N = in.nextInt(); ArrayList> G = new ArrayList<>(); for(int i = 0; i < N; i++) G.add(new ArrayList<>()); for(int i = 0; i < N - 1; i++){ int from = in.nextInt()-1; int to = in.nextInt()-1; int cost = in.nextInt(); G.get(from).add(new Edge(from, to, cost)); G.get(to).add(new Edge(to, from, cost)); } LowestCommonAncestor lca = new LowestCommonAncestor(G, 0); int Q = in.nextInt(); for(int i = 0; i < Q; i++){ int s = in.nextInt()-1, t = in.nextInt()-1; out.println(lca.dist(s, t)); } } class Edge implements Comparable{ int from; int to; int cost; public Edge(int f, int t, int c){ from = f; to = t; cost = c; } @Override public int compareTo(Edge o) { return Integer.compare(this.cost, o.cost); } } class LowestCommonAncestor { int[] vs, depth, id, d; ArrayList> T; SparseTableIndex sti; //Euler-Tour Technique public LowestCommonAncestor(ArrayList> T, int root){ vs = new int[T.size()*2-1]; depth = new int[T.size()*2-1]; id = new int[T.size()]; d = new int[T.size()]; this.T = T; dfsStack(root); sti = new SparseTableIndex(depth); } void dfsStack(int root){ ArrayDeque stack = new ArrayDeque<>(); int k = 0; stack.addLast(new int[]{0, root, -1, 0, 0}); while(!stack.isEmpty()){ int[] node = stack.removeLast(); int v = node[1], p = node[2], nd = node[3], cost = node[4]; if(node[0] == 0){ id[v] = k; vs[k] = v; depth[k] = nd; d[v] = cost; k++; for(Edge e : T.get(v)) { int to = e.to; if (to == p) continue; stack.addLast(new int[]{1, v, p, nd, -1}); stack.addLast(new int[]{0, to, v, nd+1, d[v] + e.cost}); } }else{ vs[k] = v; depth[k] = nd; k++; } } } public int lca(int u, int v){ int L = Math.min(id[u], id[v]), R = Math.max(id[u], id[v]); return vs[sti.get(L, R+1)]; } public int dist(int u, int v){ return d[u] + d[v] - 2 * d[lca(u, v)]; } class SparseTableIndex { int[][] table; int[] height; int[] v; public SparseTableIndex(int[] v){ init(v); } void init(int[] v){ this.v = Arrays.copyOf(v, v.length); int n = v.length, h = 0; while((1<>1]+1; for(int i = 0; i < n; i++) table[0][i] = i; for(int i = 1; i < h; i++) { for (int j = 0; j < n; j++) { int x = table[i - 1][j], y = table[i - 1][Math.min(j + (1 << (i - 1)), n - 1)]; table[i][j] = v[x] <= v[y] ? x : y; } } } public int get(int a, int b){ int l = height[b-a]; int x = table[l][a], y = table[l][b-(1< Integer.MAX_VALUE) throw new NumberFormatException(); return (int) nl; } public long nextLong() { try { int sign = 1; int b = input.read(); while ((b < '0' || '9' < b) && b != '-' && b != '+') { b = input.read(); } if (b == '-') { sign = -1; b = input.read(); } else if (b == '+') { b = input.read(); } long ret = b - '0'; while (true) { b = input.read(); if (b < '0' || '9' < b) return ret * sign; ret *= 10; ret += b - '0'; } } catch (IOException e) { e.printStackTrace(); return -1; } } public double nextDouble() { try { double sign = 1; int b = input.read(); while ((b < '0' || '9' < b) && b != '-' && b != '+') { b = input.read(); } if (b == '-') { sign = -1; b = input.read(); } else if (b == '+') { b = input.read(); } double ret = b - '0'; while (true) { b = input.read(); if (b < '0' || '9' < b) break; ret *= 10; ret += b - '0'; } if (b != '.') return sign * ret; double div = 1; b = input.read(); while ('0' <= b && b <= '9') { ret *= 10; ret += b - '0'; div *= 10; b = input.read(); } return sign * ret / div; } catch (IOException e) { e.printStackTrace(); return Double.NaN; } } public char nextChar() { try { int b = input.read(); while (Character.isWhitespace(b)) { b = input.read(); } return (char) b; } catch (IOException e) { e.printStackTrace(); return 0; } } public String nextStr() { try { StringBuilder sb = new StringBuilder(); int b = input.read(); while (Character.isWhitespace(b)) { b = input.read(); } while (b != -1 && !Character.isWhitespace(b)) { sb.append((char) b); b = input.read(); } return sb.toString(); } catch (IOException e) { e.printStackTrace(); return ""; } } public String nextLine() { try { StringBuilder sb = new StringBuilder(); int b = input.read(); while (b != -1 && b != '\n') { sb.append((char) b); b = input.read(); } return sb.toString(); } catch (IOException e) { e.printStackTrace(); return ""; } } public int[] nextIntArray(int n) { int[] res = new int[n]; for (int i = 0; i < n; i++) { res[i] = nextInt(); } return res; } public int[] nextIntArrayDec(int n) { int[] res = new int[n]; for (int i = 0; i < n; i++) { res[i] = nextInt() - 1; } return res; } public int[] nextIntArray1Index(int n) { int[] res = new int[n + 1]; for (int i = 0; i < n; i++) { res[i + 1] = nextInt(); } return res; } public long[] nextLongArray(int n) { long[] res = new long[n]; for (int i = 0; i < n; i++) { res[i] = nextLong(); } return res; } public long[] nextLongArrayDec(int n) { long[] res = new long[n]; for (int i = 0; i < n; i++) { res[i] = nextLong() - 1; } return res; } public long[] nextLongArray1Index(int n) { long[] res = new long[n + 1]; for (int i = 0; i < n; i++) { res[i + 1] = nextLong(); } return res; } public double[] nextDoubleArray(int n) { double[] res = new double[n]; for (int i = 0; i < n; i++) { res[i] = nextDouble(); } return res; } } }