/* -*- coding: utf-8 -*- * * 898.cc: No.898 tri-ē”«utree - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 100000; const int K = 17; /* typedef */ typedef long long ll; typedef queue qi; typedef pair pii; typedef vector vpii; /* global variables */ vpii nbrs[MAX_N]; int prts[MAX_N][K], ds[MAX_N]; ll pws[MAX_N]; /* subroutines */ int lca(int u, int v) { if (ds[u] > ds[v]) swap(u, v); for (int i = K - 1; i >= 0; i--) if (((ds[v] - ds[u]) >> i) & 1) v = prts[v][i]; if (u == v) return u; for(int i = K - 1; i >= 0; i--) if (prts[u][i] != prts[v][i]) { u = prts[u][i]; v = prts[v][i]; } return prts[u][0]; } ll pathw(int u, int v) { int a = lca(u, v); return pws[u] + pws[v] - pws[a] * 2; } /* main */ int main() { int n; scanf("%d", &n); for (int i = 1; i < n; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); nbrs[u].push_back(pii(v, w)); nbrs[v].push_back(pii(u, w)); } prts[0][0] = -1; ds[0] = 0; pws[0] = 0; qi q; q.push(0); while (! q.empty()) { int u = q.front(); q.pop(); for (int k = 0; k < K - 1; k++) prts[u][k + 1] = (prts[u][k] >= 0) ? prts[prts[u][k]][k] : -1; int &up = prts[u][0], vd = ds[u] + 1; vpii &nbru = nbrs[u]; for (vpii::iterator vit = nbru.begin(); vit != nbru.end(); vit++) { int &v = vit->first, &w = vit->second; if (v != up) { prts[v][0] = u; ds[v] = vd; pws[v] = pws[u] + w; q.push(v); } } } int qn; scanf("%d", &qn); while (qn--) { int x, y, z; scanf("%d%d%d", &x, &y, &z); ll sum = (pathw(x, y) + pathw(y, z) + pathw(z, x)) / 2; printf("%lld\n", sum); } return 0; }