#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] = eW; for (auto [i, c] : nei[u]){ if (dead[i] or i == p) continue; dfs2(i, u, c.first); dwn[u] += dwn[i]; if (eW == 0) continue; 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); int m1 = 0, m2 = 0; vector<int> v = {0, 0}; for (auto [i, c] : nei[u]){ if (dead[i]) continue; if (vec[i][ind[i]] > m1){ v.push_back(m2); m2 = m1, m1 = vec[i][ind[i]]; vec[i].erase(begin(vec[i]) + ind[i]); } else if (vec[i][ind[i]] > m2){ v.push_back(m2); m2 = vec[i][ind[i]]; vec[i].erase(begin(vec[i]) + ind[i]); } for (int j : vec[i]) v.push_back(j); } sort(rbegin(v), rend(v)); Mn[2] = min(Mn[2], Extra + dwn[u] - m1 - m2); for (int i=0, sm = m1 + m2;i<v.size();i++) sm += v[i], Mn[i+3] = min(Mn[i+3], 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'; }