#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> ans(M, 0), only(M), depth(M), sajz(M), par(M), is_off(M), cost(M), pre(M), post(M); vector<vector<pair<ll, ll>>> g(M); ll added = 0,nxt; struct SegTree { ll base=1; vector<pair<ll,ll>> T; vector<ll> L; void push(ll v, ll l, ll r) { if(L[v]==0 || v >= base) return; T[l].first += L[v]; T[r].first += L[v]; L[l] += L[v]; L[r] += L[v]; L[v] = 0; } void ustaw(ll x, ll val) { x+=base; T[x] = {0,val}; x/=2; while(x>0) { T[x] = max(T[x+x],T[x+x+1]); x/=2; } } void update(ll v, ll a, ll b, ll p, ll k, ll val) { if(b < p || k < a) return; if(p<=a && b<=k) { T[v].first += val; L[v] += val; return; } ll l=2*v; ll r=2*v+1; ll mid=(a+b)/2; push(v,l,r); update(l,a,mid,p,k,val); update(r,mid+1,b,p,k,val); T[v] = max(T[l], T[r]); } pair<ll,ll> query(ll v, ll a, ll b, ll p, ll k) { if(b < p || k < a) return {-1,0}; if(p<=a && b<=k) { return T[v]; } ll l=2*v; ll r=2*v+1; ll mid=(a+b)/2; push(v,l,r); return max(query(l,a,mid,p,k), query(r,mid+1,b,p,k)); } void init(ll n) { base = 1; while (base < n) base *= 2; T.assign(2 * base, {0, 0}); L.assign(2 * base, 0); } }; 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); } } 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]; } } ll n; SegTree st; vector<int> V; void pre_dfs(ll v, ll p) { for(auto[u,k] : g[v]) if(u==p) cost[v] = k; pre[v] = ++nxt; st.ustaw(pre[v], v); for(auto[u,k] : g[v]) { if(u==p || is_off[u]) continue; pre_dfs(u,v); } post[v] = ++nxt; st.ustaw(post[v],v); V.push_back(v); } void centroid_decomposition(ll v) { st.init(3*n+100); pre.assign(M,0); post.assign(M,0); while(V.size()) V.pop_back(); sajz_dfs(v,v); nxt=1; cost[v] = 0; pre_dfs(v,v); ll cnt = 0; if(g[v].size()<2) cnt++; ll res = only[v]; for(auto x : V) st.update(1,0,st.base-1,pre[x],post[x],cost[x]); vector<pair<ll,ll>> F; for(auto[u,k] : g[v]) { F.push_back(st.query(1,0,st.base-1,pre[u],post[u])); } sort(F.begin(), F.end()); reverse(F.begin(), F.end()); auto obsluz = [&](pair<ll, ll> para) { cnt++; ll x = para.second; res += para.first; while(cost[x] > 0) { st.update(1,0,st.base-1,pre[x],post[x],-cost[x]); cost[x]=0; x=par[x]; } if(cnt > 1) ans[cnt] = max(ans[cnt], res); ans[cnt+1] = max(ans[cnt+1], res); }; if(F.size()>=1) obsluz(F[0]); if(F.size()>=2) obsluz(F[1]); while(st.T[1].first > 0) { obsluz(st.T[1]); } } 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; } 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]); } for(auto[x,y] : edges) { auto[a,c] = x; auto[b,d] = y; ans[2] = max(ans[2], only[a] + d); ans[2] = max(ans[2], only[b] + c); } for(int i=1; i<=n; ++i) { centroid_decomposition(i); } // centroid_decomposition(1); ll q; cin >> q; while(q--) { ll x; cin >> x; cout << sum - ans[x] << "\n"; } return 0; }