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 @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) x = -1 l,r = @offset + a, @offset + b while l < r if l.odd? x = min_depth(x, @data[l]); l += l[0] end if r.odd? r -= r[0]; x = min_depth(x, @data[r]) end l >>= 1 r >>= 1 end return x end def min_depth(a,b) return b if a < 0 return a if b < 0 @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 = @data.size @data[k >> 1] = min_depth(@data[k >> 1], @data[k]) 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)) }