#include using namespace std; typedef long long ll; // LCA // verify: https://atcoder.jp/contests/abc014/submissions/9535352 vector>> v(200010); bool used[200010]; int depth[200010]; int par[200010][20]; ll dp[200020]; // 根からの深さと1つ上の親を求める. initの中で使う void dfs(int p,int d,ll cost){ used[p] = 1; depth[p] = d; dp[p]=cost; for(auto i:v[p]){ if(!used[i[0]]){ dfs(i[0],d+1,cost+i[1]); par[i[0]][0] = p; } } } // init(n, root) でダブリングテーブルを作製する, nは頂点数 void init(int n,int root=0){ for(int i=0;i=0;i--){ if(d & (1<=0;i--){ if(dif & (1<=0;i--){ if(par[a][i]!=par[b][i]){ a = par[a][i], b = par[b][i]; } } return par[a][0]; } signed main(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); ll n; cin>>n; for(int i=1;i>a>>b>>c; v[b].push_back({a,c}); v[a].push_back({b,c}); } init(n); int q; cin>>q; while(q--){ int a,b,c; cin>>a>>b>>c; ll ans = dp[a] + dp[b] + dp[c]; ans -= dp[lca(a,b)] + dp[lca(a,c)] + dp[lca(b,c)]; ans += dp[lca(a,lca(b,c))]; cout << ans << "\n"; } }