#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define repr(i, s, n) for (int i = (s); i < (int)(n); i++) #define revrep(i, n) for (int i = (n) - 1; i >= 0; i--) #define revrepr(i, s, n) for (int i = (n) - 1; i >= s; i--) #define debug(x) cerr << #x << ": " << x << "\n" #define popcnt(x) __builtin_popcount(x) using ll = long long; using P = pair; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } template istream& operator >>(istream &is, vector &v) { for (int i = 0; i < (int)v.size(); i++) cin >> v.at(i); return is; } template ostream& operator <<(ostream &os, pair p) { cout << '(' << p.first << ", " << p.second << ')'; return os; } template void print(const vector &v, const string &delimiter) { rep(i, v.size()) cout << (0 < i ? delimiter : "") << v.at(i); cout << endl; } template void print(const vector> &vv, const string &delimiter) { for (const auto &v: vv) print(v, delimiter); } const int MAX_V = 100000; const int MAX_LOG_V = log2(MAX_V) + 1; vector> graph(MAX_V); int root; vector> parent(MAX_LOG_V, vector(MAX_V + 1)); vector depth(MAX_V + 2); void dfs(int v, int p, int d) { parent.at(0).at(v) = p; depth.at(v) = d; for(int c: graph.at(v)) if (c != p) dfs(c, v, d + 1); } //O(N log N) void init(int V) { dfs(root, -1, 0); for (int k = 0; k + 1 < MAX_LOG_V; k++) { for (int v = 0; v < V; v++) { if (parent.at(k).at(v) < 0) parent.at(k + 1).at(v) = -1; else parent.at(k + 1).at(v) = parent.at(k).at(parent.at(k).at(v)); } } } //O(log N) int lca(int u, int v) { if (depth.at(u) > depth.at(v)) swap(u, v); for (int k = 0; k < MAX_LOG_V; k++) { if ((depth.at(v) - depth.at(u)) >> k & 1) v = parent.at(k).at(v); if (u == v) return u; } for (int k = MAX_LOG_V - 1; k >= 0; k--) { if (parent.at(k).at(u) != parent.at(k).at(v)) { u = parent.at(k).at(u); v = parent.at(k).at(v); } } return parent.at(0).at(u); } struct Edge { int to; ll weight; }; vector> edges(MAX_V); vector d(MAX_V, -1); void calc_dist(int v, ll dist, int pre = -1) { d[v] = dist; for (auto &&e: edges[v]) if (e.to != pre) calc_dist(e.to, dist + e.weight, v); } ll get_dist(int u, int v) { return d[u] + d[v] - d[lca(u, v)] * 2; } int main() { int n; cin >> n; rep(i, n - 1) { int u, v, w; cin >> u >> v >> w; graph[u].push_back(v); graph[v].push_back(u); edges[u].push_back(Edge{v, w}); edges[v].push_back(Edge{u, w}); } root = 0; init(n); calc_dist(0, 0); int q; cin >> q; rep(_q, q) { int x, y, z; cin >> x >> y >> z; int a = lca(lca(x, y), z); ll ans = get_dist(a, x) + get_dist(a, y) + get_dist(a, z) - get_dist(a, lca(x, y)) - get_dist(a, lca(x, z)) - get_dist(a, lca(y, z)); cout << ans << endl; } }