#include #include #include using namespace std; vector> no[100000]; vector o; int in[100000], out[100000], st[32][300000]; long long d[100000]; void tour(int n, int e) { d[n] = e; in[n] = o.size(); o.push_back(n); for (auto i : no[n]) { if (d[i.first] == 0) { tour(i.first, e + i.second); o.push_back(n); } } out[n] = o.size(); } int lca(int x, int y) { if (in[y] < in[x]) swap(x, y); int u = in[x], v = in[y]; int i = 0; while (1 << (i + 1) <= v - u) i++; if (d[st[i][u]] < d[st[i][v-(1<> n; for (int i = 0; i < n - 1; i++) { cin >> u >> v >> w; no[u].push_back({v, w}); no[v].push_back({u, w}); } tour(0, 1); for (int i = 0; i < o.size(); i++) { st[0][i] = o[i]; } for (int i = 1; (1 << i) <= o.size(); i++) { for (int j = 0; j < o.size(); j++) { if (d[st[i -1][j]] < d[st[i - 1][min(j + (1 << (i - 1)), (int)o.size() - 1)]]) { st[i][j] = st[i - 1][j]; } else { st[i][j] = st[i - 1][min(j + (1 << (i - 1)), (int)o.size() - 1)]; } } } cin >> q; for (int i = 0; i < q; i++) { cin >> x >> y >> z; u = lca(x, y); v = lca(y, z); w = lca(z, x); if (u == v) cout << d[x] + d[y] + d[z] - d[w] - 2 * d[u] << endl; else if (v == w) cout << d[x] + d[y] + d[z] - d[u] - 2 * d[v] << endl; else cout << d[x] + d[y] + d[z] - d[v] - 2 * d[u] << endl; } // for (int i = 0; i < o.size(); i++) cout << o[i] << " "; // cout << endl; // for (int i = 0; i < n; i++) cout << d[i] << " "; // cout << endl; // for (int i = 0; i < 4; i++) { // for (int j = 0; j < o.size(); j++) { // cout << st[i][j] << " "; // } // cout << endl; // } // cout << u << " " << v << " " << w << endl; }