#include <bits/stdc++.h> using namespace std; typedef long long int ll; #define int ll const int N = 1<<18; const ll INF = 1e18; struct SegTree { pair<ll, int> Tree[2*N]; ll Delta[2*N]; SegTree() { for(int i = 0; i < N; i++) Tree[i+N] = {0, i}; for(int i = N-1; i >= 1; i--) Tree[i] = max(Tree[2*i], Tree[2*i + 1]); } void lazy(int u) { Tree[u].first += Delta[u]; if(u < N) { Delta[2*u] += Delta[u]; Delta[2*u + 1] += Delta[u]; } Delta[u] = 0; } void update(int u, int low, int high, int A, int B, ll C) { lazy(u); if(low > B || high < A) return; if(low >= A && high <= B) { Delta[u] += C; lazy(u); return; } update(2*u, low, (low+high)/2, A, B, C); update(2*u + 1, (low+high)/2 + 1, high, A, B, C); Tree[u] = max(Tree[2*u], Tree[2*u + 1]); } }; SegTree T1; vector<pair<int, ll>> Graph[N]; ll SumEdges[N]; pair<ll, int> BestVertex[N]; tuple<ll, int, int> Diameter = {INF, 0, 0}; pair<int, int> Segment[N]; int Pre_rev[N]; pair<int, ll> Parents[N]; bitset<N> Active; ll Solution[N]; void DFS1(int u, int parent) { BestVertex[u] = {0, u}; for(auto [v, d] : Graph[u]) { if(v != parent) { DFS1(v, u); SumEdges[u] += SumEdges[v] + d; if(BestVertex[v].first + d > BestVertex[u].first) BestVertex[u] = {BestVertex[v].first + d, BestVertex[v].second}; } } } void DFS2(int u, int parent, ll outside) { pair<ll, int> help1 = {0, 0}; pair<ll, int> help2 = {0, 0}; for(auto [v, d] : Graph[u]) { if(v == parent) outside += d; } if(u != BestVertex[u].second && get<0>(Diameter) > SumEdges[u] - BestVertex[u].first + outside) { Diameter = {SumEdges[u] - BestVertex[u].first + outside, u, BestVertex[u].second}; } for(auto [v, d] : Graph[u]) { if(v != parent) { DFS2(v, u, outside + SumEdges[u] - (SumEdges[v] + d)); if(BestVertex[v].first + d > help1.first) { swap(help1, help2); help1 = {BestVertex[v].first + d, BestVertex[v].second}; } else if(BestVertex[v].first + d > help2.first) help2 = {BestVertex[v].first + d, BestVertex[v].second}; } } if(Graph[u].size() - (parent != 0) >= 2) { if(get<0>(Diameter) > (SumEdges[u] - (help1.first + help2.first)) + outside) Diameter = {(SumEdges[u] - (help1.first + help2.first)) + outside, help1.second, help2.second}; } } int pre_cnt = 1; void DFS3(int u, int parent) { Segment[u].first = pre_cnt; Pre_rev[pre_cnt] = u; pre_cnt++; for(auto [v, d] : Graph[u]) { if(v != parent) { DFS3(v, u); Segment[v].second = pre_cnt-1; Parents[v] = {u, d}; T1.update(1, 0, N-1, Segment[v].first, Segment[v].second, d); } } } ll FindOne(int u, int parent, ll outside) { for(auto [v, d] : Graph[u]) { if(v == parent) outside += d; } ll sol = SumEdges[u] + outside; for(auto [v, d] : Graph[u]) { if(v != parent) sol = min(sol, FindOne(v, u, outside + SumEdges[u] - (SumEdges[v] + d))); } return sol; } void Fix(int u) { while(!Active[u]) { T1.update(1, 0, N-1, Segment[u].first, Segment[u].second, -Parents[u].second); Active[u] = 1; u = Parents[u].first; } } void Solve(int n) { Solution[1] = FindOne(1, 0, 0); Solution[2] = get<0>(Diameter); DFS3(get<1>(Diameter), 0); Active[get<1>(Diameter)] = 1; Fix(get<2>(Diameter)); for(int i = 3; i <= n; i++) { if(Solution[i-1] == 0) Solution[i] = 0; else { int u = T1.Tree[1].second; ll x = T1.Tree[1].first; Fix(Pre_rev[u]); Solution[i] = Solution[i-1] - x; } } } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, a, b, c, d; cin >> n; for(int i = 0; i < n-1; i++) { cin >> a >> b >> c >> d; Graph[a].push_back({b, c}); Graph[b].push_back({a, d}); } DFS1(1, 0); DFS2(1, 0, 0); Solve(n); int q, w; cin >> q; while(q --> 0) { cin >> w; cout << Solution[w] << "\n"; } return 0; }