#include #include #include #include #include #include using namespace std; #define int long long #define endl "\n" const long long INF = (long long)1e18; const long long MOD = 1'000'000'007; string yn(bool f){return f?"Yes":"No";} string YN(bool f){return f?"YES":"NO";} struct edge{ int to, cost; }; vector> G; vector depth; vector> table; void dfs(int node, int per, int dep){ table[0][node] = per; depth[node] = dep; for(edge e : G[node]){ if(e.to == per) continue; dfs(e.to, node, dep+1); } } void init(int V){ int logV = 1; for(int i = 1; i <= V; i <<= 1, logV++); depth.clear(); depth.resize(V+1); table.clear(); table.resize(logV, vector(V+1,-1)); dfs(1, -1, 0); for(int k = 0; k + 1 < logV; k++){ for(int v = 0; v < V; v++){ if(table[k][v] < 0) table[k+1][v] = -1; else table[k+1][v] = table[k][table[k][v]]; } } } int lca(int u, int v){ if(depth[u] > depth[v]) swap(u, v); for(int k = 0; k < table.size(); k++){ if((depth[v] - depth[u]) >> k & 1){ v = table[k][v]; } } if(u == v) return u; for(int k = table.size()-1; k >= 0; k--){ if(table[k][u] != table[k][v]){ u = table[k][u]; v = table[k][v]; } } return table[0][u]; } vector cost; void dfs2(int now = 1, int pre = -1, int sum = 0){ cost[now] = sum; for(int i = 0; i < G[now].size(); i++){ if(G[now][i].to == pre) continue; dfs2(G[now][i].to,now,sum + G[now][i].cost); } } signed main(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout<>> G; cin>>N; G.resize(N+1); cost.resize(N+1); for(int i = 0; i < N-1; i++){ int a, b, c; cin>>a>>b>>c; a++;b++; G[a].push_back(edge{b,c}); G[b].push_back(edge{a,c}); // G[a].push_back(make_pair(b,c)); // G[b].push_back(make_pair(a,c)); } init(N+1); dfs2(); cin>>Q; // for(int i = 1; i <= N; i++){ // cout<<"i = "<