#pragma GCC optimize("O3") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using P = pair; using T = tuple; template inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;} template inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;} constexpr int MOD = 1e9 + 7; constexpr int inf = 1e9; constexpr long long INF = 1e18; #define all(a) (a).begin(), (a).end() int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; class LCA{ public: static const int MAX_LOG_V = 30; vector parent[MAX_LOG_V]; // 親を2^k回辿って到達する頂点(根を通り過ぎる場合は-1) vector depth; void init(int V, vector> &G){ int root = 0; for(int i=0; i> &G){ parent[0][v] = p; depth[v] = d; for(int i=0; i depth[v]) swap(u, v); for(int k=0; k> k & 1){ v = parent[k][v]; } } if(u == v) return u; for(int k=MAX_LOG_V-1; k>=0; k--){ if(parent[k][u] != parent[k][v]){ u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } int dist(int u, int v){ return depth[u] + depth[v] - 2 * depth[calc_lca(u, v)]; } bool is_in(int u, int v, int a){ return (dist(u, a) + dist(a, v) == dist(u, v)); } }; vector sum(100010); void calc_sum_dfs(int cv, int pv, vector> &G){ for(auto nxt : G[cv]){ int nv, cost; tie(nv, cost) = nxt; if(nv == pv) continue; sum[nv] = sum[cv] + cost; calc_sum_dfs(nv, cv, G); } } int main(){ cin.tie(0); ios::sync_with_stdio(false); int n; cin>>n; vector u(n-1), v(n-1), w(n-1); vector> G(n); for(int i=0; i>u[i]>>v[i]>>w[i]; G[u[i]].emplace_back(v[i]); G[v[i]].emplace_back(u[i]); } LCA lca; lca.init(n, G); vector> G2(n); for(int i=0; i>q; while(q--){ int x, y, z; cin>>x>>y>>z; ll cur1 = sum[x] + sum[y] - 2 * sum[lca.calc_lca(x, y)]; ll cur2 = sum[x] + sum[z] - 2 * sum[lca.calc_lca(x, z)]; ll cur3 = sum[y] + sum[z] - 2 * sum[lca.calc_lca(y, z)]; cout << (cur1 + cur2 + cur3) / 2 << endl; } return 0; }