//#pragma GCC optimize("Ofast")
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <set>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back //emplace_back
#define pp pop_back
#define pii pair<ll, ll> //pair<int, int>
#define all(x) (x).begin(),(x).end()
#define mp(a,b) make_pair(a , b)
#define lb lower_bound
#define ub upper_bound
#define sz(x) (ll)(x).size()
#define F first
#define S second
#define bg(x) (x).begin()
#define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
#define debug(x) cout << #x << " : " << x << endl << flush
#define endl '\n'
#define arr(x) array<ll , (x)>
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);
ll Sum(ll a , ll b , ll MOD)
{
a %= MOD;
b %= MOD;
a += b;
return a % MOD;
}
ll Mul(ll a , ll b , ll MOD)
{
a %= MOD;
b %= MOD;
a *= b;
return a % MOD;
}
ll Pow(ll a , ll b , ll MOD)
{
ll res = 1;
while(b)
{
if((b & 1))res = Mul(res , a , MOD);
a = Mul(a , a , MOD);
b >>= 1;
}
return res;
}
ll Min(ll a , ll b)
{
if(a > b)return b;
return a;
}
ll Max(ll a , ll b)
{
if(a > b)return a;
return b;
}
ll Ceil(ll a , ll b)
{
if(a % b)return (a/b)+1;
return a/b;
}
/////////////////////
//VALS
const ll maxn = 2e5;
const ll INF = 1e18;
ll n;
set<arr(3)> adj[maxn];
ll q;
ll barg;
ll par[maxn];
ll dp[maxn];
ll dp1;
ll root;
/////////////////////
//FUNCTIONS
void dfs_1_1(ll u, ll p)
{
par[u] = p;
for(auto v : adj[u])
{
if(v[0] == p)continue;
dp1 += v[1];
dfs_1_1(v[0], u);
}
}
void dfs_1_2(ll u, ll val)
{
for(auto v : adj[u])
{
if(v[0] == par[u])continue;
//debug(u);
//debug(v[0]);
dp[1] = Min(dp[1], val - v[1] + v[2]);
//debug(val - v[1] + v[2]);
dfs_1_2(v[0], val - v[1] + v[2]);
}
}
void compress(ll u)
{
if(u != root and sz(adj[u]) == 2)
{
auto ch = (*adj[u].begin());
auto p = (*adj[u].rbegin());
if(ch[0] == par[u])
swap(ch,p);
par[ch[0]] = p[0];
adj[ch[0]].erase(adj[ch[0]].find({u, ch[2], ch[1]}));
adj[p[0]].erase(adj[p[0]].find({u, p[2], p[1]}));
adj[p[0]].insert({ch[0], p[2]+ch[1], p[1]+ch[2]});
adj[ch[0]].insert({p[0], p[1]+ch[2], p[2]+ch[1]});
}
for(auto v : adj[u])
if(v[0] != par[u])
compress(v[0]);
}
/////////////////////
//SOLVE
void solve()
{
cin >> n;
For(i,n-1)
{
ll a, b ,c ,d;
cin >> a >> b >> c >> d;
a--;
b--;
adj[a].insert({b,c,d});
adj[b].insert({a,d,c});
}
barg = 0;
For(i,n)if(sz(adj[i]) == 1)barg++;
for(int i = barg; i <= n; i++)dp[i] = 0;
root = 0;
For(i,n)
if(sz(adj[i]) != 1)
{
root = i;
break;
}
dfs_1_1(root, root);
dp[1] = dp1;
//debug(dp[1]);
dfs_1_2(root, dp1);
compress(root);
set<arr(3)> s;
For(i,n)
if(sz(adj[i]) == 1)
{
auto u = (*adj[i].begin());
s.insert({u[2],u[1], i});
}
/*
debug(sz(s));
for(auto u : s)
{
debug(u[0]);
debug(u[1]);
debug(u[2]);
cout << "AAAAAA\n" << flush;
}
*/
ll cur = 0;
barg--;
//debug(barg);
/*
6
1 6 6 12
6 2 5 16
1 4 13 4
5 1 19 3
3 1 9 13
100
2
*/
for(int i = barg; i >= 2; i--)
{
//cout <<"AAAAAAA\n" << flush;
auto bst = (*s.begin());
s.erase(bst);
//debug(bst[0]);
//debug(bst[1]);
//debug(bst[2]);
cur += bst[0];
dp[i] = cur;
//bst -> {0 -> bottom to top, 1 -> top to bottom, 2 -> index}
//cout << "BF\n" << flush;
adj[par[bst[2]]].erase(adj[par[bst[2]]].find({bst[2], bst[0], bst[1]}));
//cout << "AF\n" << flush;
if(i != 1 and sz(adj[par[bst[2]]]) == 2 and par[bst[2]] != root)
{
//cout << ":P\n" << flush;
ll u = par[bst[2]];
auto ch = (*adj[u].begin());
auto p = (*adj[u].rbegin());
if(ch[0] == par[u])
swap(ch,p);
par[ch[0]] = p[0];
adj[ch[0]].erase(adj[ch[0]].find({u, ch[2], ch[1]}));//
adj[p[0]].erase(adj[p[0]].find({u, p[2], p[1]}));
adj[p[0]].insert({ch[0], p[2]+ch[1], p[1]+ch[2]});
adj[ch[0]].insert({p[0], p[1]+ch[2], p[2]+ch[1]});
s.erase(s.find({ch[1], ch[2], u}));
s.insert({p[2]+ch[1], p[1]+ch[2], p[0]});
}
//cout << ";l\n" << flush;
}
cin >> q;
while(q--)
{
//cout << "@_@\n" << endl;
ll e;
cin >> e;
cout << dp[e] << endl;
}
}
/////////////////////
//MAIN
int main()
{
FAST;
ll t = 1;
// cin >> t;
while(t--)
{
solve();
}
}
/////////////////////
/*
ZZZZZZZ A M M IIIIIII N N
Z A A M M M M I NN N
Z A A M M M M I N N N
Z AAAAAAA M M M I N N N
Z A A M M I N N N
Z A A M M I N NN
ZZZZZZZ A A M M IIIIIII N N TREE
*///#pragma GCC optimize("Ofast")
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <set>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back //emplace_back
#define pp pop_back
#define pii pair<ll, ll> //pair<int, int>
#define all(x) (x).begin(),(x).end()
#define mp(a,b) make_pair(a , b)
#define lb lower_bound
#define ub upper_bound
#define sz(x) (ll)(x).size()
#define F first
#define S second
#define bg(x) (x).begin()
#define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
#define debug(x) cout << #x << " : " << x << endl << flush
#define endl '\n'
#define arr(x) array<ll , (x)>
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);
ll Sum(ll a , ll b , ll MOD)
{
a %= MOD;
b %= MOD;
a += b;
return a % MOD;
}
ll Mul(ll a , ll b , ll MOD)
{
a %= MOD;
b %= MOD;
a *= b;
return a % MOD;
}
ll Pow(ll a , ll b , ll MOD)
{
ll res = 1;
while(b)
{
if((b & 1))res = Mul(res , a , MOD);
a = Mul(a , a , MOD);
b >>= 1;
}
return res;
}
ll Min(ll a , ll b)
{
if(a > b)return b;
return a;
}
ll Max(ll a , ll b)
{
if(a > b)return a;
return b;
}
ll Ceil(ll a , ll b)
{
if(a % b)return (a/b)+1;
return a/b;
}
/////////////////////
//VALS
const ll maxn = 2e5;
const ll INF = 1e18;
ll n;
set<arr(3)> adj[maxn];
ll q;
ll barg;
ll par[maxn];
ll dp[maxn];
ll dp1;
ll root;
/////////////////////
//FUNCTIONS
void dfs_1_1(ll u, ll p)
{
par[u] = p;
for(auto v : adj[u])
{
if(v[0] == p)continue;
dp1 += v[1];
dfs_1_1(v[0], u);
}
}
void dfs_1_2(ll u, ll val)
{
for(auto v : adj[u])
{
if(v[0] == par[u])continue;
//debug(u);
//debug(v[0]);
dp[1] = Min(dp[1], val - v[1] + v[2]);
//debug(val - v[1] + v[2]);
dfs_1_2(v[0], val - v[1] + v[2]);
}
}
void compress(ll u)
{
if(u != root and sz(adj[u]) == 2)
{
auto ch = (*adj[u].begin());
auto p = (*adj[u].rbegin());
if(ch[0] == par[u])
swap(ch,p);
par[ch[0]] = p[0];
adj[ch[0]].erase(adj[ch[0]].find({u, ch[2], ch[1]}));
adj[p[0]].erase(adj[p[0]].find({u, p[2], p[1]}));
adj[p[0]].insert({ch[0], p[2]+ch[1], p[1]+ch[2]});
adj[ch[0]].insert({p[0], p[1]+ch[2], p[2]+ch[1]});
}
for(auto v : adj[u])
if(v[0] != par[u])
compress(v[0]);
}
/////////////////////
//SOLVE
void solve()
{
cin >> n;
For(i,n-1)
{
ll a, b ,c ,d;
cin >> a >> b >> c >> d;
a--;
b--;
adj[a].insert({b,c,d});
adj[b].insert({a,d,c});
}
barg = 0;
For(i,n)if(sz(adj[i]) == 1)barg++;
for(int i = barg; i <= n; i++)dp[i] = 0;
root = 0;
For(i,n)
if(sz(adj[i]) != 1)
{
root = i;
break;
}
dfs_1_1(root, root);
dp[1] = dp1;
//debug(dp[1]);
dfs_1_2(root, dp1);
compress(root);
set<arr(3)> s;
For(i,n)
if(sz(adj[i]) == 1)
{
auto u = (*adj[i].begin());
s.insert({u[2],u[1], i});
}
/*
debug(sz(s));
for(auto u : s)
{
debug(u[0]);
debug(u[1]);
debug(u[2]);
cout << "AAAAAA\n" << flush;
}
*/
ll cur = 0;
barg--;
//debug(barg);
/*
6
1 6 6 12
6 2 5 16
1 4 13 4
5 1 19 3
3 1 9 13
100
2
*/
for(int i = barg; i >= 2; i--)
{
//cout <<"AAAAAAA\n" << flush;
auto bst = (*s.begin());
s.erase(bst);
//debug(bst[0]);
//debug(bst[1]);
//debug(bst[2]);
cur += bst[0];
dp[i] = cur;
//bst -> {0 -> bottom to top, 1 -> top to bottom, 2 -> index}
//cout << "BF\n" << flush;
adj[par[bst[2]]].erase(adj[par[bst[2]]].find({bst[2], bst[0], bst[1]}));
//cout << "AF\n" << flush;
if(i != 1 and sz(adj[par[bst[2]]]) == 2 and par[bst[2]] != root)
{
//cout << ":P\n" << flush;
ll u = par[bst[2]];
auto ch = (*adj[u].begin());
auto p = (*adj[u].rbegin());
if(ch[0] == par[u])
swap(ch,p);
par[ch[0]] = p[0];
adj[ch[0]].erase(adj[ch[0]].find({u, ch[2], ch[1]}));//
adj[p[0]].erase(adj[p[0]].find({u, p[2], p[1]}));
adj[p[0]].insert({ch[0], p[2]+ch[1], p[1]+ch[2]});
adj[ch[0]].insert({p[0], p[1]+ch[2], p[2]+ch[1]});
s.erase(s.find({ch[1], ch[2], u}));
s.insert({p[2]+ch[1], p[1]+ch[2], p[0]});
}
//cout << ";l\n" << flush;
}
cin >> q;
while(q--)
{
//cout << "@_@\n" << endl;
ll e;
cin >> e;
cout << dp[e] << endl;
}
}
/////////////////////
//MAIN
int main()
{
FAST;
ll t = 1;
// cin >> t;
while(t--)
{
solve();
}
}
/////////////////////
/*
ZZZZZZZ A M M IIIIIII N N
Z A A M M M M I NN N
Z A A M M M M I N N N
Z AAAAAAA M M M I N N N
Z A A M M I N N N
Z A A M M I N NN
ZZZZZZZ A A M M IIIIIII N N TREE
*/
Compilation message
designated_cities.cpp: In function 'void solve()':
designated_cities.cpp:26:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
26 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
| ^
designated_cities.cpp:148:2: note: in expansion of macro 'For'
148 | For(i,n-1)
| ^~~
designated_cities.cpp:26:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
26 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
| ^
designated_cities.cpp:160:2: note: in expansion of macro 'For'
160 | For(i,n)if(sz(adj[i]) == 1)barg++;
| ^~~
designated_cities.cpp:26:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
26 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
| ^
designated_cities.cpp:165:2: note: in expansion of macro 'For'
165 | For(i,n)
| ^~~
designated_cities.cpp:26:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
26 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
| ^
designated_cities.cpp:182:2: note: in expansion of macro 'For'
182 | For(i,n)
| ^~~
designated_cities.cpp: At global scope:
designated_cities.cpp:315:4: error: redefinition of 'long long int Sum(long long int, long long int, long long int)'
315 | ll Sum(ll a , ll b , ll MOD)
| ^~~
designated_cities.cpp:34:4: note: 'long long int Sum(long long int, long long int, long long int)' previously defined here
34 | ll Sum(ll a , ll b , ll MOD)
| ^~~
designated_cities.cpp:323:4: error: redefinition of 'long long int Mul(long long int, long long int, long long int)'
323 | ll Mul(ll a , ll b , ll MOD)
| ^~~
designated_cities.cpp:42:4: note: 'long long int Mul(long long int, long long int, long long int)' previously defined here
42 | ll Mul(ll a , ll b , ll MOD)
| ^~~
designated_cities.cpp:331:4: error: redefinition of 'long long int Pow(long long int, long long int, long long int)'
331 | ll Pow(ll a , ll b , ll MOD)
| ^~~
designated_cities.cpp:50:4: note: 'long long int Pow(long long int, long long int, long long int)' previously defined here
50 | ll Pow(ll a , ll b , ll MOD)
| ^~~
designated_cities.cpp:343:4: error: redefinition of 'long long int Min(long long int, long long int)'
343 | ll Min(ll a , ll b)
| ^~~
designated_cities.cpp:62:4: note: 'long long int Min(long long int, long long int)' previously defined here
62 | ll Min(ll a , ll b)
| ^~~
designated_cities.cpp:349:4: error: redefinition of 'long long int Max(long long int, long long int)'
349 | ll Max(ll a , ll b)
| ^~~
designated_cities.cpp:68:4: note: 'long long int Max(long long int, long long int)' previously defined here
68 | ll Max(ll a , ll b)
| ^~~
designated_cities.cpp:355:4: error: redefinition of 'long long int Ceil(long long int, long long int)'
355 | ll Ceil(ll a , ll b)
| ^~~~
designated_cities.cpp:74:4: note: 'long long int Ceil(long long int, long long int)' previously defined here
74 | ll Ceil(ll a , ll b)
| ^~~~
designated_cities.cpp:363:10: error: redefinition of 'const long long int maxn'
363 | const ll maxn = 2e5;
| ^~~~
designated_cities.cpp:82:10: note: 'const long long int maxn' previously defined here
82 | const ll maxn = 2e5;
| ^~~~
designated_cities.cpp:364:10: error: redefinition of 'const long long int INF'
364 | const ll INF = 1e18;
| ^~~
designated_cities.cpp:83:10: note: 'const long long int INF' previously defined here
83 | const ll INF = 1e18;
| ^~~
designated_cities.cpp:366:4: error: redefinition of 'long long int n'
366 | ll n;
| ^
designated_cities.cpp:85:4: note: 'long long int n' previously declared here
85 | ll n;
| ^
designated_cities.cpp:367:13: error: redefinition of 'std::set<std::array<long long int, 3> > adj [200000]'
367 | set<arr(3)> adj[maxn];
| ^~~
designated_cities.cpp:86:13: note: 'std::set<std::array<long long int, 3> > adj [200000]' previously declared here
86 | set<arr(3)> adj[maxn];
| ^~~
designated_cities.cpp:368:4: error: redefinition of 'long long int q'
368 | ll q;
| ^
designated_cities.cpp:87:4: note: 'long long int q' previously declared here
87 | ll q;
| ^
designated_cities.cpp:369:4: error: redefinition of 'long long int barg'
369 | ll barg;
| ^~~~
designated_cities.cpp:88:4: note: 'long long int barg' previously declared here
88 | ll barg;
| ^~~~
designated_cities.cpp:370:4: error: redefinition of 'long long int par [200000]'
370 | ll par[maxn];
| ^~~
designated_cities.cpp:89:4: note: 'long long int par [200000]' previously declared here
89 | ll par[maxn];
| ^~~
designated_cities.cpp:371:4: error: redefinition of 'long long int dp [200000]'
371 | ll dp[maxn];
| ^~
designated_cities.cpp:90:4: note: 'long long int dp [200000]' previously declared here
90 | ll dp[maxn];
| ^~
designated_cities.cpp:372:4: error: redefinition of 'long long int dp1'
372 | ll dp1;
| ^~~
designated_cities.cpp:91:4: note: 'long long int dp1' previously declared here
91 | ll dp1;
| ^~~
designated_cities.cpp:373:4: error: redefinition of 'long long int root'
373 | ll root;
| ^~~~
designated_cities.cpp:92:4: note: 'long long int root' previously declared here
92 | ll root;
| ^~~~
designated_cities.cpp:376:6: error: redefinition of 'void dfs_1_1(long long int, long long int)'
376 | void dfs_1_1(ll u, ll p)
| ^~~~~~~
designated_cities.cpp:95:6: note: 'void dfs_1_1(long long int, long long int)' previously defined here
95 | void dfs_1_1(ll u, ll p)
| ^~~~~~~
designated_cities.cpp:389:6: error: redefinition of 'void dfs_1_2(long long int, long long int)'
389 | void dfs_1_2(ll u, ll val)
| ^~~~~~~
designated_cities.cpp:108:6: note: 'void dfs_1_2(long long int, long long int)' previously defined here
108 | void dfs_1_2(ll u, ll val)
| ^~~~~~~
designated_cities.cpp:402:6: error: redefinition of 'void compress(long long int)'
402 | void compress(ll u)
| ^~~~~~~~
designated_cities.cpp:121:6: note: 'void compress(long long int)' previously defined here
121 | void compress(ll u)
| ^~~~~~~~
designated_cities.cpp:425:6: error: redefinition of 'void solve()'
425 | void solve()
| ^~~~~
designated_cities.cpp:144:6: note: 'void solve()' previously defined here
144 | void solve()
| ^~~~~
designated_cities.cpp: In function 'void solve()':
designated_cities.cpp:307:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
307 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
| ^
designated_cities.cpp:429:2: note: in expansion of macro 'For'
429 | For(i,n-1)
| ^~~
designated_cities.cpp:307:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
307 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
| ^
designated_cities.cpp:441:2: note: in expansion of macro 'For'
441 | For(i,n)if(sz(adj[i]) == 1)barg++;
| ^~~
designated_cities.cpp:307:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
307 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
| ^
designated_cities.cpp:446:2: note: in expansion of macro 'For'
446 | For(i,n)
| ^~~
designated_cities.cpp:307:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
307 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
| ^
designated_cities.cpp:463:2: note: in expansion of macro 'For'
463 | For(i,n)
| ^~~
designated_cities.cpp: At global scope:
designated_cities.cpp:544:5: error: redefinition of 'int main()'
544 | int main()
| ^~~~
designated_cities.cpp:263:5: note: 'int main()' previously defined here
263 | int main()
| ^~~~
