#include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const int MAX_V = 500000; struct Node { int v; int depth; Node(int v = -1, int depth = -1) { this->v = v; this->depth = depth; } bool operator<(const Node &n) const { return depth < n.depth; } }; class StaticRMQ { public: vector dat; int N; void init(int n) { N = 1; while (N < n) N *= 2; for (int i = 0; i < 2 * N - 1; ++i) { dat.push_back(Node(-1, MAX_V)); } } void update(int k, Node a) { k += N - 1; dat[k] = a; while (k > 0) { k = (k - 1) / 2; dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]); } } ll find_min(int l, int r) { return query(l, r, 0, 0, N).v; } private: Node query(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return Node(-1, MAX_V); if (a <= l && r <= b) { return dat[k]; } else { Node vl = query(a, b, k * 2 + 1, l, (l + r) / 2); Node vr = query(a, b, k * 2 + 2, (l + r) / 2, r); return min(vl, vr); } } }; class LCA { public: vector vs; vector depth; vector id; vector > G; StaticRMQ rmq; LCA(int N, int root, vector > _G) { G = _G; int k = 0; vs = vector(2 * N - 1); depth = vector(2 * N - 1); id = vector(N, -1); dfs(root, -1, 0, k); rmq.init(k); for (int i = 0; i < k; ++i) { rmq.update(i, Node(vs[i], depth[i])); } } int find_parent(int u, int v) { return rmq.find_min(min(id[u], id[v]), max(id[u], id[v])); } private: void dfs(int v, int p, int d, int &k) { id[v] = k; vs[k] = v; depth[k++] = d; for (int i = 0; i < G[v].size(); ++i) { if (G[v][i] != p) { dfs(G[v][i], v, d + 1, k); vs[k] = v; depth[k++] = d; } } } }; vector W[100010]; ll dist[100010]; vector> G(100010); void dfs(int v, int parent, ll w) { dist[v] = w; for (int i = 0; i < G[v].size(); ++i) { int u = G[v][i]; ll nw = w + W[v][i]; if (u == parent) continue; dfs(u, v, nw); } } void setup_dist() { memset(dist, 0, sizeof(dist)); dfs(0, -1, 0); } ll calc_cost(int x, int y, int z, LCA &lca) { int p = lca.find_parent(x, y); ll fw = dist[x] + dist[y] - 2 * dist[p]; int sp = lca.find_parent(p, z); ll sw = dist[p] + dist[z] - 2 * dist[sp]; // fprintf(stderr, "x: %d, y: %d, p: %d, fw: %lld\n", x, y, p, fw); return fw + sw; } int main() { int N; cin >> N; for (int i = 0; i < N - 1; ++i) { ll u, v, w; cin >> u >> v >> w; G[u].push_back(v); G[v].push_back(u); W[u].push_back(w); W[v].push_back(w); } setup_dist(); LCA lca(N, 0, G); int Q; cin >> Q; for (int i = 0; i < Q; ++i) { int x, y, z; cin >> x >> y >> z; ll c1 = calc_cost(x, y, z, lca); ll c2 = calc_cost(x, z, y, lca); ll c3 = calc_cost(y, z, x, lca); // fprintf(stderr, "c1: %lld, c2: %lld, c3: %lld\n", c1, c2, c3); cout << min(c1, min(c2, c3)) << endl; } return 0; }