#include <iostream> #include <vector> #include <algorithm> using namespace std; #define int long long const int N = 1<<18; vector<pair<int, pair<int, int>>> nei[N]; vector<int> vec[N]; int ch[N], dead[N], ind[N], dwn[N], tot, Mn[N]; void dfs1(int u, int p){ ch[u] = 1; for (auto [i, c] : nei[u]) if (i != p and !dead[i]) dfs1(i, u), ch[u] += ch[i]; } int cent(int u, int p, int sz){ for (auto [i, c] : nei[u]) if (i != p and !dead[i] and ch[i] * 2 >= sz) return cent(i, u, sz); return u; } void dfs2(int u, int p, int eW){ vec[u] = {0}, ind[u] = 0, dwn[u] = 0; for (auto [i, c] : nei[u]){ if (dead[i] or i == p) continue; dfs2(i, u, c.first); dwn[u] += dwn[i] + c.first; if (vec[i].size() > vec[u].size()) swap(vec[i], vec[u]), swap(ind[i], ind[u]); for (int w : vec[i]){ if (w > vec[u][ind[u]]) ind[u] = vec[u].size(); vec[u].push_back(w); } } vec[u][ind[u]] += eW; } void dfs3(int u, int p, int eW){ dwn[u] = eW; for (auto [i, c] : nei[u]){ if (i == p) continue; dfs3(i, u, c.first); dwn[u] += dwn[i]; } } void dfs4(int u, int p, int up = 0){ Mn[1] = min(Mn[1], dwn[u] + up); for (auto [i, c] : nei[u]){ if (i == p) continue; dfs4(i, u, up + dwn[u] - dwn[i] - c.first + c.second); } } void decomp(int u, int Extra){ dfs1(u, -1); u = cent(u, -1, ch[u]); dfs2(u, -1, 0); sort(begin(vec[u]), end(vec[u])); for (int i=2, sm = vec[u].back();i<=vec[u].size();i++) sm += vec[u][vec[u].size() - i], Mn[i] = min(Mn[i], Extra + dwn[u] - sm); dead[u] = 1; for (auto [i, c] : nei[u]){ if (dead[i]) continue; decomp(i, Extra + dwn[u] - dwn[i] - c.first + c.second); } } signed main(){ int n, q, e; cin>>n; for (int i=1;i<n;i++){ Mn[i] = 1e17; int a, b, c, d; cin>>a>>b>>c>>d; nei[a].push_back({b, {c, d}}); nei[b].push_back({a, {d, c}}); } dfs3(1, -1, 0); dfs4(1, -1); decomp(1, 0); for (int i=1;i<=n;i++) Mn[i+1] = min(Mn[i+1], Mn[i]); cin>>q; while (q--) cin>>e, cout<<Mn[e]<<'\n'; }