#pragma region Macros // #pragma GCC target("avx,avx2,fma") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include // #include using namespace std; using namespace __gnu_pbds; // using namespace __gnu_cxx; // #include // #include // #include // using namespace atcoder; // #include // namespace mp = boost::multiprecision; // using Bint = mp::cpp_int; #define TO_STRING(var) # var #define pb emplace_back #define int ll #define endl '\n' using ll = long long; using ld = long double; const ld PI = acos(-1); const ld EPS = 1e-10; const ll INFL = 1LL << 61; const int MOD = 998244353; // const int MOD = 1000000007; __attribute__((constructor)) void constructor() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); } template class modint{ public: int val = 0; modint(int x = 0) { while (x < 0) x += mod; val = x % mod; } modint(const modint &r) { val = r.val; } // コピーコンストラクタ modint operator -(){ return modint(-val); } // 単項 modint operator +(const modint &r) { return modint(*this) += r; } modint operator -(const modint &r) { return modint(*this) -= r; } modint operator *(const modint &r) { return modint(*this) *= r; } modint operator /(const modint &r) { return modint(*this) /= r; } modint &operator +=(const modint &r) { val += r.val; if (val >= mod) val -= mod; return *this; } modint &operator -=(const modint &r) { if (val < r.val) val += mod; val -= r.val; return *this; } modint &operator *=(const modint &r) { val = val * r.val % mod; return *this; } modint &operator /=(const modint &r) { int a = r.val, b = mod, u = 1, v = 0; while (b) { int t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } val = val * u % mod; if (val < 0) val += mod; return *this; } bool operator ==(const modint& r) { return this -> val == r.val; } bool operator <(const modint& r) { return this -> val < r.val; } bool operator !=(const modint& r) { return this -> val != r.val; } }; using mint = modint; istream &operator >>(istream &is, mint& x) { int t; is >> t; x = t; return (is); } ostream &operator <<(ostream &os, const mint& x) { return os << x.val; } mint modpow(const mint &a, int n) { if (n == 0) return 1; mint t = modpow(a, n / 2); t = t * t; if (n & 1) t = t * a; return t; } int modpow(int x, int N, int mod) { int ret = 1; while (N > 0) { if (N % 2 == 1) ret = ret * x % mod; x = x * x % mod; N /= 2; } return ret; } int ceil(int x, int y) { return (x > 0 ? (x + y - 1) / y : x / y); } #pragma endregion struct Edge { int from, to; int cost; Edge(int to, int cost) : from(-1), to(to), cost(cost) {} Edge(int from, int to, int cost) : from(from), to(to), cost(cost) {} Edge &operator=(const int &x) { to = x; return *this; } operator int() const { return to; } }; using Graph = vector>; struct LCA { vector> parent; // parent[k][u]:= u の 2^k 先の親 vector depth; // root からの深さ vector dist; // root からの距離(重みの総和) vector> mx; // mx[u][v]:= u-vパスに含まれる辺の重みの最大値 LCA(const Graph &G, int root) { init(G, root); } // 初期化 void init(const Graph &G, int root) { int N = G.size(); int k = 1; while ((1LL << k) < N) k++; parent.assign(k, vector(N, -1)); mx.assign(k, vector(N, -1)); depth.assign(N, -1); dist.assign(N, -1); dfs(G, root, -1, 0, 0); for (int i = 0; i + 1 < k; i++) { // 2^i for (int v = 0; v < N; v++) { if (parent[i][v] < 0) { parent[i + 1][v] = -1; } else { parent[i + 1][v] = parent[i][parent[i][v]]; mx[i + 1][v] = max(mx[i][parent[i][v]], mx[i][v]); } } } } // 根からの距離と1つ先の頂点を求める void dfs(const Graph &G, int v, int par, int dp, int di) { parent[0][v] = par; depth[v] = dp; dist[v] = di; for (auto e : G[v]) { if (e.to == par) continue; dfs(G, e.to, v, dp + 1, di + e.cost); mx[0][e.to] = e.cost; } } // void dfs(const vector> &G, int v, int p, int d) { // parent[0][v] = p; // depth[v] = d; // for (int nv : G[v]) { // if (nv == p) continue; // dfs(G, nv, v, d + 1); // } // } // 重みなしグラフ int query(int u, int v) { if (depth[u] < depth[v]) swap(u, v); // u の方が深いとする int k = parent.size(); // LCA までの距離を同じにする for (int i = 0; i < k; i++) { if ((depth[u] - depth[v]) >> i & 1) { u = parent[i][u]; } } // 二分探索で LCA を求める if (u == v) return u; for (int i = k - 1; i >= 0; i--) { if (parent[i][u] != parent[i][v]) { u = parent[i][u]; v = parent[i][v]; } } return parent[0][u]; } int query2(int u, int v) { // 最大値用 if (depth[u] < depth[v]) swap(u, v); // u の方が深いとする int k = parent.size(); int ret = 0; // LCA までの距離を同じにする for (int i = 0; i < k; i++) { if ((depth[u] - depth[v]) >> i & 1) { ret = max(ret, mx[i][u]); u = parent[i][u]; } } // 二分探索で LCA を求める if (u == v) return ret; for (int i = k - 1; i >= 0; i--) { if (parent[i][u] != parent[i][v]) { ret = max(ret, max(mx[i][u], mx[i][v])); u = parent[i][u]; v = parent[i][v]; } } return max(ret, max(mx[0][u], mx[0][v])); } // 重みなしグラフとして考えた時の2点間の距離 int get_dist(int u, int v) { return depth[u] + depth[v] - 2 * depth[query(u, v)]; } // 2点間の距離 int get_dist2(int u, int v) { return dist[u] + dist[v] - 2 * dist[query(u, v)]; } // u-vパスに含まれる辺の重みの最大値 int get_max(int u, int v) { return query2(u, v); } // u-vパス上にaがあるか bool is_on_path(int u, int v, int a) { return get_dist(u, a) + get_dist(a, v) == get_dist(u, v); } }; signed main() { 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].pb(v, c); G[v].pb(u, c); } auto lca = LCA(G, 0); // 前処理 int Q; cin >> Q; for (int i = 0; i < Q; i++) { int u, v; cin >> u >> v; u--; v--; cout << lca.get_dist2(u, v) << endl; } }