#ifdef LOCAL #define _GLIBCXX_DEBUG #define __clock__ #else #pragma GCC optimize("Ofast") #endif #include using namespace std; using ll = long long; using ld = long double; using VI = vector; using VV = vector; using VS = vector; using PII = pair; // tourist set template string to_string(pair p); template string to_string(tuple p); template string to_string(tuple p); string to_string(const string& s) { return '"' + s + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(bool b) { return (b ? "true" : "false"); } string to_string(vector v) { bool first = true; string res = "{"; for (int i = 0; i < static_cast(v.size()); i++) { if (!first) { res += ", "; } first = false; res += to_string(v[i]); } res += "}"; return res; } template string to_string(bitset v) { string res = ""; for (size_t i = 0; i < N; i++) { res += static_cast('0' + v[i]); } return res; } template string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); } res += "}"; return res; } template string to_string(pair p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template string to_string(tuple p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")"; } template string to_string(tuple p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")"; } void debug_out() { cerr << '\n'; } template void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif // tourist set end templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b()) #define MP make_pair #define p_yes() p("Yes") #define p_no() p("No") ll SUM(VI& V){ return accumulate(ALL(V), 0LL); } ll MIN(VI& V){return *min_element(ALL(V));} ll MAX(VI& V){return *max_element(ALL(V));} void print_vector(VI& V){ ll n = V.size(); rep(i, n){ if(i) cout << ' '; cout << V[i]; } cout << endl; } ll gcd(ll a,ll b){ if(b == 0) return a; return gcd(b,a%b); } ll lcm(ll a,ll b){ ll g = gcd(a,b); return a / g * b; } // long double using ld = long double; #define EPS (1e-14) #define equals(a,b) (fabs((a)-(b)) < EPS) void no(){p_no(); exit(0);} void yes(){p_yes(); exit(0);} const ll mod = 1e9 + 7; const ll inf = 1e18; const double PI = acos(-1); struct Edge{ ll to; ll cost; Edge(ll to, ll cost): to(to), cost(cost) {} Edge(){ to = 0; cost = 0; } }; struct Node{ ll distance; ll index; Node(ll d, ll i){ distance = d; index = i; } Node(){} bool operator<(const Node &another) const { return distance < another.distance; } bool operator>(const Node &another) const { return distance > another.distance; } }; struct Dijkstra{ vector d; vector > graph; vector done; // ノード数を入れる void initialize(ll size){ d.resize(size); done.resize(size); graph.resize(size); reset(); } void reset(){ ll N = graph.size(); FOR(i, 0, N){ d[i] = inf; done[i] = false; } } ll distance(int i){ if((ll)d.size()<=i) return -1; return d[i]; } void print_graph(){ FOR(i, 0, (ll)graph.size()){ cout << i << " -> "; for(auto edge : graph[i]){ cout << edge.to << " "; } cout << endl; } p("distance"); FOR(i, 0, (ll)graph.size()){ ll d = distance(i); cout << i << " " << d << endl; } } void register_edge(ll a, ll b, ll cost){ if(cost<0){ p("ダイクストラなのに負コストですがいいですか?");exit(0); } auto edge = Edge(b, cost); graph[a].push_back(edge); } // 双方向 void register_edge2(ll a, ll b, ll cost){ register_edge(a, b, cost); register_edge(b, a, cost); } void calc_shortest_path(ll from=0){ ll N = graph.size(); if(from<0 || from>=N){ cout << "index error" << endl; exit(0); } priority_queue, greater > que; auto node = Node(); // 始点 node.index = from; node.distance = 0; que.push(node); while(!que.empty()){ // 1番distanceが小さいノード Node n = que.top(); que.pop(); if(done[n.index]){ continue; } done[n.index] = true; d[n.index] = n.distance; auto edge_list = graph[n.index]; for(auto edge : edge_list){ // 短くなるノードがあれば if(!done[edge.to] && n.distance + edge.cost < d[edge.to]){ ll shorter_distance = n.distance + edge.cost; que.push(Node(shorter_distance, edge.to)); } } } } }; // LCA set VV G; const int N_MAX = 200010; const int MAX_LOG_V = 20; // log2(200000)=17.6 ll depth[N_MAX] = {}; ll parent[MAX_LOG_V][N_MAX] = {}; void dfs(ll index, ll prev, ll _depth){ depth[index] = _depth; parent[0][index] = prev; for(ll to : G[index]){ if(to==prev){ continue; } dfs(to, index, _depth+1); } return; } ll LCA(ll a, ll b){ if(a==b){ return a; } // aよりbが深い(または同じ)と仮定する if(depth[a] > depth[b]){ swap(a, b); } // bを根側に辿っていく ll diff_depth = depth[b] - depth[a]; FOR(k, 0, MAX_LOG_V){ if(diff_depth >> k & 1){ b = parent[k][b]; } } // aとbの深さが揃った if(a==b){ return a; } // 大きい歩幅で共通親までジャンプ for(int k=MAX_LOG_V-1; k>=0; k--){ if(parent[k][a] != parent[k][b]){ a = parent[k][a]; b = parent[k][b]; } } // 1つ上がLCA return parent[0][a]; } void prepare_LCA(ll N, ll root=0){ dfs(root, -1, 0); // ダブリングで親 2^k FOR(k, 1, MAX_LOG_V){ // FOR(i, 1, N+1){ FOR(i, 0, N){ ll p = parent[k-1][i]; if(p==-1) continue; parent[k][i] = parent[k-1][p]; } } } // LCA set end int main(){ cin.tie(0); ios::sync_with_stdio(false); // input ll N; cin>>N; G.resize(N); // 距離情報なし Dijkstra dij; dij.initialize(N); rep(i,N-1){ ll a,b,c;cin>>a>>b>>c; a--;b--; G[a].push_back(b); G[b].push_back(a); dij.register_edge2(a,b,c); } prepare_LCA(N, 0); dij.calc_shortest_path(0); ll Q;cin>>Q; while(Q--){ ll u,v;cin>>u>>v; u--;v--; ll lca = LCA(u,v); ll dist = dij.distance(u) + dij.distance(v) - 2*dij.distance(lca); p(dist); } return 0; }