#include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll #define ft first #define sc second #define pb push_back #define all(x) x.begin(), x.end() #define pi pair<int, int> #define vi vector<int> #define tii tuple<int, int, int> #define tiii tuple<int, int, int, int> #define tiiii tuple<int, int, int, int, int> #define vpi vector<pi> #define vtii vector<tii> #define vtiii vector<tiii> const int N = (1 << 20), MOD = 1e9 + 7, INF = int(1e18); vpi graf[N]; tii edg[N]; int d[N], val[N], sz[N], id[N], p[N], pe[N], rev[N]; int e(int a, int b, int idx){ auto [x, y, z] = edg[idx]; if(a == x) return y; return z; } int dfs1(int u, int v, int b){ int w = b; for(auto [i, j] : graf[u]){ if(i == v) continue; w = max(w, dfs1(i, u, b + e(u, i, j) - e(i, u, j))); } return w; } tii dp[N][2]; void dfs2(int u, int v){ dp[u][0] = {0, u, -1}; dp[u][1] = {-1, -1, -1}; tii mx1 = {-1, -1, -1}, mx2 = mx1; for(auto [i, j] : graf[u]){ if(i == v) continue; dfs2(i, u); auto [a, b, c] = dp[i][0]; tii w = {a + e(u, i, j), b, c}; dp[u][0] = max(w, dp[u][0]); if(w > mx1){ mx2 = mx1; mx1 = w; }else if(w > mx2){ mx2 = w; } auto [x, y, z] = dp[i][1]; w = {x + e(u, i, j) - e(i, u, j), y, z}; dp[u][1] = max(dp[u][1], w); } auto [a, b, c] = mx1; auto [x, y, z] = mx2; dp[u][1] = max(dp[u][1], {a + x, b, y}); auto [a1, b1, c1] = dp[u][0]; dp[u][1] = max(dp[u][1], {a1, u, b1}); } int odp[N]; void dfs3(int u, int v, int &t){ p[u] = v; d[u] = d[v] + 1; sz[u] = 1; id[u] = ++t; rev[t] = u; for(auto [i, j] : graf[u]){ if(i == v) continue; val[i] = val[u] + e(u, i, j); pe[i] = j; dfs3(i, u, t); sz[u] += sz[i]; } } struct tree{ pi t[2 * N]; int lz[2 * N]; tree(){ for(int i = N; i < 2 * N; i++) t[i] = {0, i - N}; for(int i = N - 1; i > 0; i--) t[i] = max(t[2 * i], t[2 * i + 1]); } void lazy(int u){ t[u].ft += lz[u]; if(u < N){ lz[2 * u] += lz[u]; lz[2 * u + 1] += lz[u]; } lz[u] = 0; } void upd(int u, int l, int h, int A, int B, int V){ lazy(u); if(l > B || h < A) return; if(l >= A && h <= B){ lz[u] += V; lazy(u); if(V == INF) t[u].ft = INF; return; } upd(2 * u, l, (l + h) / 2, A, B, V); upd(2 * u + 1, (l + h) / 2 + 1, h, A, B ,V); t[u] = max(t[2 * u], t[2 * u + 1]); } pi que(){ lazy(1); return t[1]; } }; tree tri; bool vis[N]; void del_edge(int x){ tri.upd(1, 0, N - 1, id[x], id[x] + sz[x] - 1, -e(p[x], x, pe[x])); vis[x] = 1; } void solve(){ int n; cin >> n; int S = 0; for(int i = 1; i < n; i++){ int a, b, c, d; cin >> a >> b >> c >> d; graf[a].pb({b, i}); graf[b].pb({a, i}); edg[i] = {a, c, d}; S += c + d; } int s = 0; int t = 0; dfs2(1, 1); auto [z, x, y] = dp[1][1]; dfs3(x, x, t); for(int i = 1; i <= n; i++){ if(i != x) s += e(i, p[i], pe[i]); } odp[1] = S - s - dfs1(x, x, 0); dfs2(x, x); auto [z1, x1, y1] = dp[x][1]; odp[2] = S - s - z1; for(int i = 1; i <= n; i++) tri.upd(1, 0, N - 1, id[i], id[i], val[i]); while(x != y){ del_edge(y); y = p[y]; } for(int i = 3; i <= n; i++){ if(odp[i - 1] == 0) break; pi akt = tri.que(); odp[i] = odp[i - 1] - akt.ft; int a = rev[akt.sc]; while(!vis[a]){ del_edge(a); a = p[a]; } } int q; cin >> q; while(q--){ int vw; cin >> vw; cout << odp[vw] << "\n"; } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); // random_device rd; // mt19937_64 gen(rd()); int t = 1; // cin >> t; // t = 1; while(t--){ solve(); } return 0; }