#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #include #include #include #include //#include //using namespace atcoder; using namespace std; using i32 = int_fast32_t; using i64 = int_fast64_t; using usize = size_t; using u32 = uint_fast32_t; using u64 = uint_fast64_t; using i128 = __int128_t; using u128 = __uint128_t; using ld = long double; template using vec = vector; #define rep(i, n) for (i32 i = 0; i < (i32)(n); ++i) #define all(a) (a).begin(),(a).end() #define rall(a) (a).rbegin(),(a).rend() #define len(hoge) (i64)((hoge).size()) using P = pair; template class LCA { public: vector depth; const int_fast32_t dig; vector>g; vector> cost; vector costs; vector> doubling; LCA(int_fast64_t n) : depth(n), costs(n), cost(n), g(n),dig(n) { doubling.assign(dig, vector(n, -1)); } void addedge(int_fast32_t u, int_fast32_t v, int_fast64_t c = 0) { g[u].emplace_back(v); cost[u].emplace_back(c); g[v].emplace_back(u); cost[v].emplace_back(c); } void dfs(int_fast32_t now, int_fast32_t par = -1, int_fast32_t d = 0, int_fast64_t c = 0) { doubling[0][now] = par; depth[now] = d; costs[now] = c; rep(i,len(g[now])) { if (g[now][i] != par)dfs(g[now][i], now, d + 1, c + cost[now][i]); } } void construct() { dfs(0); for (int_fast32_t i = 0; i < dig - 1; i++) { for (int_fast32_t j = 0; j < doubling[i].size(); j++) { if (doubling[i][j] == -1)doubling[i + 1][j] = -1; else doubling[i + 1][j] = doubling[i][doubling[i][j]]; } } } int_fast32_t query_answer(int_fast32_t u, int_fast32_t v) { if (depth[u] > depth[v])swap(u, v); for (int_fast32_t i = dig - 1; 0 <= i; i--) { if (((depth[v] - depth[u]) >> i) & 1) v = doubling[i][v]; } if (u == v) return u; for (int_fast32_t i = dig - 1; 0 <= i; --i) { if (doubling[i][u] != doubling[i][v]) { u = doubling[i][u]; v = doubling[i][v]; } } return doubling[0][u]; } int_fast32_t length(int_fast32_t u,int_fast32_t v){ return depth[u] + depth[v] - 2 * depth[query_answer(u,v)]; } int_fast64_t dist(int_fast32_t u,int_fast32_t v){ return costs[u] + costs[v] - 2 * costs[query_answer(u,v)]; } bool isOnPath(int_fast32_t u, int_fast32_t v,int_fast32_t x){ return length(u,x) + length(v,x) == length(u,v); } }; int main() { ios::sync_with_stdio(false); std::cin.tie(nullptr); i32 n, q; cin >> n; LCA lca(n); rep(i, n - 1) { i32 a, b; i64 c; cin >> a >> b >> c; a--, b--; lca.addedge(a,b,c); } lca.construct(); cin >> q; rep(i, q) { i32 s, t; cin >> s >> t; cout << lca.dist(s - 1,t - 1) << endl; } }