// ~Be name khoda~ //
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define cl clear
#define endll '\n'
const int maxn = 1e6 + 10;
const int maxn5 = 2e5 + 10;
const int maxnt = 1e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 2e18;
int n;
ll ans1 = -1;
ll ans = -1;
int ccnt = 0, den[maxn5];
bool mark[maxn5];
vector <pair<int, int>> adj[maxn5];
ll c[maxn5], best1[maxn5], up[maxn5];
int par[maxn5], ti = -1, st[maxn5], ft[maxn5], ver[maxn5];
ll edgepar[maxn5], sumall[maxn5], lazy[maxnt], out[maxn5];
ll ex[maxn5];
pair<ll, int> farr[maxn5], mx[maxnt];
pair<int, int> req[maxn5];
inline void dfsdown(int v, int par){
best1[v] = 0;
for(auto [u, id] : adj[v]) if(u != par){
dfsdown(u, v);
best1[u] += c[id];
best1[v] += best1[u];
ex[u] = c[id];
}
return;
}
inline void dfsup(int v, int par){
ll sum = 0;
for(auto [u, id] : adj[v]){
if(u != par)
sum += best1[u];
else
up[v] += c[id];
}
for(auto [u, id] : adj[v]) if(u != par){
up[u] = up[v] + sum - best1[u];
dfsup(u, v);
}
return;
}
inline void dfsfar1(int v, int par){
mx[v] = {0, v};
den[v] = v;
for(auto [u, id] : adj[v]) if(u != par){
dfsfar1(u, v);
if(mx[v] <= mx[u]){
mx[v] = mx[u];
den[v] = u;
}
}
for(auto [u, id] : adj[v]) if(u == par)
mx[v].fi += c[id];
//cout << "so right " << v << ' ' << mx[v].se << endl;
return;
}
inline void dfsfar2(int v, int par){
ll ex = 0;
for(auto [u, id] : adj[v]){
if(u != par && u != den[v]){
farr[u] = max(farr[v], mx[v]);
farr[u].fi += c[id];
dfsfar2(u, v);
}
else if(u == den[v])
ex = c[id];
}
if(den[v] == v)
return;
pair <ll, int> tmp = farr[v];
for(auto [u, id] : adj[v]) if(u != par && u != den[v]){
tmp = max(tmp, mx[u]);
}
farr[den[v]] = tmp;
farr[den[v]].fi += ex;
dfsfar2(den[v], v);
return;
}
inline void dfs(int v, int parr){
par[v] = parr;
st[v] = ++ti;
ver[ti] = v;
for(auto [u, id] : adj[v]) if(u == parr){
sumall[v] += c[id];
edgepar[v] = c[id];
}
for(auto [u, id] : adj[v]){
if(u != parr){
sumall[u] += sumall[v];
dfs(u, v);
}
}
ft[v] = ti;
return;
}
inline void build(int l, int r, int v){
if(r - l == 1){
mx[v].se = ver[l];
mx[v].fi = 0;
if(adj[ver[l]].size() == 1){
mx[v].fi = sumall[ver[l]];
}
return;
}
int mid = (l + r) >> 1;
build(l, mid, v * 2);
build(mid, r, v * 2 + 1);
mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
return;
}
inline void add(int l, int r, int lq, int rq, ll val, int v){
if(rq <= l || r <= lq)
return;
if(lq <= l && r <= rq){
lazy[v] += val;
mx[v].fi += val;
return;
}
int mid = (l + r) >> 1;
add(l, mid, lq, rq, val, v * 2);
add(mid, r, lq, rq, val, v * 2 + 1);
mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
mx[v].fi += lazy[v];
return;
}
inline void cons(int v){
if(mark[v])
return;
ans += edgepar[v];
add(0, n, st[v], ft[v] + 1, -edgepar[v], 1);
mark[v] = true;
cons(par[v]);
return;
}
inline ll find_1(){
dfsdown(0, -1);
dfsup(0, -1);
ans1 = 0;
for(int i = 0; i < n; i++){
//cout << i << ' ' << best1[i] << ' ' << up[i] << '\n';
best1[i] += up[i] - ex[i];
ans1 = max(ans1, best1[i]);
}
//cout << "WELL " << ans1 << '\n';
return ans1;
}
inline void find_2(){
dfsfar1(0, -1);
farr[0] = {0, 0};
dfsfar2(0, -1);
int optz = 0;
for(int i = 0; i < n; i++) if(adj[i].size() == 1){
ll val = best1[i] + farr[i].fi;
//cout << "& " << i << ' ' << best1[i] << ' ' << farr[i].fi << ' ' << farr[i].se << endl;
if(val >= ans){
optz = i;
ans = val;
}
}
dfs(optz, -1);
build(0, n, 1);
mark[optz] = true;
cons(farr[optz].se);
ans -= farr[optz].fi;
//cout << "allright " << optz << endl;
return;
}
inline void upd(){
if(ccnt == 0)
return;
int v = mx[1].se;
cons(v);
ccnt--;
return;
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin >> n;
int ind = 0;
ll tot = 0;
for(int i = 0; i < n - 1; i++){
int a, b; cin >> a >> b >> c[ind] >> c[ind + 1];
a--; b--;
adj[a].pb({b, ind + 1});
adj[b].pb({a, ind});
tot += c[ind] + c[ind + 1];
ind += 2;
}
ccnt = 0;
for(int i = 0; i < n; i++) if(adj[i].size() == 1)
ccnt++;
int q; cin >> q;
for(int i = 0; i < q; i++){
cin >> req[i].fi;
req[i].se = i;
}
sort(req, req + q);
find_1();
find_2();
int last = 2;
for(int i = 0; i < q; i++){
if(req[i].fi == 1){
out[req[i].se] = ans1;
//cout << "well done " << i << ' ' << req[i].se << ' ' << out[req[i].se] << ' ' << ans1 << '\n';
}
else{
while(last < req[i].fi){
last++;
upd();
}
out[req[i].se] = ans;
}
}
for(int i = 0; i < q; i++)
cout << tot - out[i] << '\n';
}
/*
15
14 5 12 7
14 12 6 5
14 10 14 16
9 14 16 12
13 7 4 15
1 3 8 1
6 7 15 13
15 4 4 6
9 1 12 6
13 1 7 6
13 4 5 15
2 6 11 19
8 4 12 7
13 11 14 5
1
3
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5072 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5024 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5072 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5072 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
5032 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5072 KB |
Output is correct |
| 2 |
Runtime error |
77 ms |
25252 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
5072 KB |
Output is correct |
| 2 |
Runtime error |
71 ms |
25196 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5072 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5024 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5072 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5072 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
5032 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5072 KB |
Output is correct |
| 2 |
Runtime error |
77 ms |
25252 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5072 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5024 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5072 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5072 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
5032 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
