#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; } int dfs2(int u, int p, int eW){ dwn[u] = eW; int mx = 0; for (auto [i, c] : nei[u]){ if (dead[i] or i == p) continue; mx = max(mx, dfs2(i, u, c.first)); dwn[u] += dwn[i]; } return mx + 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 Up){ dfs1(u, -1); u = cent(u, -1, ch[u]); int m1 = 0, m2 = 0; for (auto [i, c] : nei[u]){ if (dead[i]) continue; int a = dfs2(i, u, c.first); if (a > m1) m2 = m1, m1 = a; else if (a > m2) m2 = a; } Mn[2] = min(Mn[2], Up + dwn[u] - m1 - m2); dead[u] = 1; for (auto [i, c] : nei[u]){ if (dead[i]) continue; decomp(i, Up + 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'; }