#include #include "atcoder/all" #define debug cout << "OK" << endl; template inline bool chmax(T& a, const T b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin(T& a, const T b) { if (a > b) { a = b; return true; } return false; } inline int Code(char c) { if ('A' <= c and c <= 'Z')return (int)(c - 'A'); if ('a' <= c and c <= 'z')return (int)(c - 'a'); if ('0' <= c and c <= '9')return (int)(c - '0'); assert(false); } using namespace std; using namespace atcoder; #define int long long constexpr int MOD = 998244353; constexpr int INF = (1LL << 62); using minit = modint998244353; template ostream& operator << (ostream& st, const vector &v) { for (const T value : v) { st << value << " "; } return st; } template istream& operator >> (istream& st, vector& v) { for (T &value : v) { st >> value; } return st; } // class LCA_C { public: vector> parent; vector dist; vector distC; vector>> G; LCA_C(const vector>>& gr) { init(gr); } void dfs(long long v, long long p, long long d,long long d2) { parent[0][v] = p; dist[v] = d; distC[v] = d2; for (pair e : G[v]) { if (e.first == p)continue; dfs(e.first, v, d + 1, d2 + e.second); } return; } void init(const vector>>& gr) { G = gr; parent.assign(33, vector(G.size(), -1LL)); dist.assign(G.size(), -1LL); distC.assign(G.size(), -1LL); dfs(0LL, -1LL, 0LL,0LL); for (int i = 0; i < 32; i++) { for (int j = 0; j < G.size(); j++) { if (parent[i][j] < 0LL) { parent[i + 1][j] = -1LL; } else { parent[i + 1][j] = parent[i][parent[i][j]]; } } } return; } long long lca(long long u, long long v) { if (dist[u] < dist[v])swap(u, v); long long between = dist[u] - dist[v]; for (int i = 0; i < 33; i++) { if (between & (1LL << i)) { u = parent[i][u]; } } if (u == v)return u; for (int i = 32; i >= 0; i--) { if (parent[i][u] != parent[i][v]) { u = parent[i][u]; v = parent[i][v]; } } assert(parent[0][u] == parent[0][v]); return parent[0][u]; } long long get_dist(long long u, long long v) { return distC[u] + distC[v] - 2 * distC[lca(u, v)]; } bool on_path(long long u, long long v, long long a) { return get_dist(u, v) == get_dist(u, a) + get_dist(v, a); } }; // void solve() { int N; cin >> N; vector>> G(N); for (int i = 0; i < N - 1; i++) { int u, v, c; cin >> u >> v >> c; u--; v--; G[u].push_back({ v, c }); G[v].push_back({ u, c }); } LCA_C C(G); int Q; cin >> Q; for (int i = 0; i < Q; i++) { int a, b; cin >> a >> b; a--; b--; cout << C.get_dist(a, b) << endl; } return; } signed main() { int T = 1; // cin >> T; for (int i = 0; i < T; i++) solve(); return 0; } /* * わらびのコードこーどすぺーす (σ・∀・)σゲッツ!! */