#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> typedef long long ll; using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; ll M = 200'010; vector<ll> depth(M), only(M), ans(M), is_off(M); vector<vector<pair<ll, ll>>> g(M); ll nxt; void only_dfs(ll v, ll p) { depth[v] = depth[p] + 1; for(auto[u,k] : g[v]) { if(u==p) continue; only[u] += only[v]; only_dfs(u,v); } } ll n; vector<ll> par(M), sajz(M); void sajz_dfs(ll v, ll p) { sajz[v] = 1; par[v] = p; for(auto[u,k] : g[v]) { if(u==p || is_off[u]) continue; sajz_dfs(u,v); sajz[v] += sajz[u]; } } vector<ll> cost(M), vis(M); ll find_centroid(ll v, ll ts) { for(auto[u,k] : g[v]) { if(is_off[u]) continue; if(u==par[v]) { if(ts-sajz[v] > ts/2) return find_centroid(u,ts); } else { if(sajz[u] > ts/2) return find_centroid(u,ts); } } return v; } struct ds { ll mx=-1; vector<pair<ll, ll>> S; void insert(pair<ll, ll> v) { if(mx==-1 || v > S[mx]) mx = S.size(); S.push_back(v); } void dodaj(ll v) { S[mx].first += v; } }; ds mw_dfs(ll v, ll p) { pair<ll, ll> heavy = {-1,0}; for(auto[u,k] : g[v]) { if(u==p) cost[v] = k; if(u==p || is_off[u]) continue; heavy = max(heavy, {sajz[u], u}); } if(heavy.first==-1) { ds my_ds; my_ds.insert({0,v}); my_ds.dodaj(cost[v]); return my_ds; } ds my_ds = mw_dfs(heavy.second, v); for(auto[u,k] : g[v]) { if(u==p || is_off[u] || u==heavy.second) continue; ds hds = mw_dfs(u,v); for(auto x : hds.S) my_ds.insert(x); } my_ds.insert({0,v}); my_ds.dodaj(cost[v]); return my_ds; } void centroid_decomposition(ll v) { sajz_dfs(v, v); ll ctr = find_centroid(v,sajz[v]); sajz_dfs(ctr,ctr); if(sajz[ctr]==1) { is_off[ctr] = 1; return; } ll cnt = 0; ll res = only[ctr]; // cout << res << "\n"; cost[ctr] = 0; vector<pair<ll, ll>> F = {{0,ctr}}, ALL; for(auto[u,k] : g[ctr]) { if(is_off[u]) continue; ds leaves = mw_dfs(u,ctr); F.push_back(leaves.S[leaves.mx]); for(auto x : leaves.S) ALL.push_back(x); } sort(F.begin(), F.end()); reverse(F.begin(), F.end()); while(F.size() > 2) F.pop_back(); for(auto[x,y] : F) { if(vis[y]) continue; vis[y] = 1; res += x; cnt++; if(cnt > 1) ans[cnt] = max(ans[cnt], res); } sort(ALL.begin(), ALL.end()); reverse(ALL.begin(), ALL.end()); for(auto[x,y] : ALL) { if(vis[y]) continue; vis[y] = 1; res += x; cnt++; if(cnt > 1) ans[cnt] = max(ans[cnt], res); } for(auto[x,y] : ALL) { vis[y] = 0; } is_off[ctr] = 1; for(auto[u,k] : g[ctr]) if(!is_off[u]) centroid_decomposition(u); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; ll sum = 0; vector<pair<pair<ll, ll>, pair<ll, ll>>> edges; for(ll i=1; i<n; ++i) { ll a,b,c,d; cin >> a >> b >> c >> d; swap(c,d); g[a].push_back({b,c}); g[b].push_back({a,d}); edges.push_back({{a,c},{b,d}}); sum += c + d; } ll added = 0; only_dfs(1,0); for(auto[x,y] : edges) { if(depth[y.first] > depth[x.first]) swap(x,y); auto[a,c] = x; auto[b,d] = y; only[a] += c-d; added += d; } only_dfs(1,0); for(ll i=1; i<=n; ++i) { only[i] += added; ans[1] = max(ans[1], only[i]); } centroid_decomposition(1); for(ll i=2; i<=n; ++i) ans[i] = max(ans[i], ans[i-1]); ll q; cin >> q; while(q--) { ll x; cin >> x; cout << sum - ans[x] << "\n"; } return 0; }