class LCA class << self def create(g, s = 0) parent = Array.new(g.size) active = Array.new(g.size, 0) depth = Array.new(g.size) tour = [] u = parent[s] = s depth[s] = 0 tour << s while true if (j = active[u]) >= g[u].size break if u == s u = parent[u] tour << u active[u] += 1 else v, d = g[u][j] if !parent[v] parent[v] = u depth[v] = depth[u] + d u = v tour << u else active[u] += 1 end end end new(tour, depth) end end def initialize(tour, depth) @tour = tour @depth = depth @ord = Array.new(depth.size) @offset = 1 << @tour.size.bit_length @data = Array.new(@offset << 1, -1) build! end def dist(a,b) c = lca(a,b) @depth[a] + @depth[b] - 2 * @depth[c] end def lca(a,b) a,b = b,a if @ord[b] < @ord[a] find_min(@ord[a], @ord[b] + 1) end private def find_min(a, b, k = 1, l = 0, r = @offset) return -1 if b <= l || r <= a return @data[k] if a <= l && r <= b mid = (l + r) / 2 return min_depth(find_min(a, b, 2 * k, l, mid), find_min(a, b, 2 * k + 1, mid, r)) end def min_depth(a,b) a < 0 ? b : b < 0 ? a : @depth[a] < @depth[b] ? a : b end def build! @tour.each_with_index do |u, i| @data[@offset + i] = u @ord[u] = i if !@ord[u] end k = @offset @data[k] = min_depth(@data[2 * k], @data[2 * k + 1]) while (k -= 1) > 0 end end N = gets.to_i G = Array.new(N + 1){ [] } (N - 1).times do u, v, d = gets.split.map(&:to_i) G[u] << [v, d] G[v] << [u, d] end lca = LCA.create(G, 1) Q = gets.to_i puts Q.times.map{ lca.dist(*gets.split.map(&:to_i)) }