#include<bits/stdc++.h>
#define ll long long
#define int long long
const int nmax = 2e5 + 5, N = 1e5;
const ll oo = 1e18 + 1, base = 311;
const int lg = 19, M = 10;
const ll mod = 998244353, mod2 = 1e9 + 5277;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;
int n, q;
map<int, int> mp[nmax];
ll f[nmax];
vector<int> adj[nmax], leaf;
void dfs_1(int u, int p){
bool ok = 1;
for(auto v : adj[u]){
if(v == p) continue;
dfs_1(v, u);
f[u] += f[v] + mp[u][v];
ok = 0;
}
if(ok) leaf.push_back(u);
}
ll pre[nmax], suf[nmax], g[nmax];
struct node{
int u,v, x, y;
}a[nmax];
void dfs_2(int u, int p){
int k = adj[u].size();
pre[0] = suf[k + 1] = 0;
for(int i = 1; i <= k; ++i){
int v = adj[u][i -1];
pre[i] = pre[i - 1];
if(v == p) continue;
pre[i] += mp[u][v] + f[v];
}
for(int i = k; i >= 1; --i){
int v = adj[u][i - 1];
suf[i] = suf[i + 1];
if(v == p) continue;
suf[i] += mp[u][v] + f[v];
}
for(int i = 1; i <= k; ++i){
int v = adj[u][i - 1];
if(v == p) continue;
g[v] = g[u] + mp[v][u] + pre[i - 1] + suf[i + 1];
dfs_2(v, u);
}
}
ll sum = 0;
int h[nmax], one[nmax];
ll dp[nmax], nchain = 1;
void dfs_3(int u, int p){
for(auto v : adj[u]){
if(v == p) continue;
sum -= mp[u][v];
dfs_3(v, u);
h[u] = max(h[v] + mp[v][u], h[u]);
}
}
void dfs_4(int u, int p){
for(auto v : adj[u]){
one[v] = h[v] + mp[v][u];
}
sort(adj[u].begin(), adj[u].end(), [](int a, int b){
return one[a] > one[b];
});
int idx = -1;
for(auto v : adj[u]){
if(v == p) continue;
idx = v;
break;
}
if(idx != -1){
dp[nchain] += mp[idx][u];
dfs_4(idx, u);
}
for(auto v : adj[u]){
if(v == p || idx == v) continue;
++nchain;
dp[nchain] += mp[v][u];
dfs_4(v, u);
}
}
ll S, T, dcu[nmax], ma = -oo, rev[nmax];
void dfs(int u, int p){
dcu[u] = u;
for(auto v : adj[u]){
if(v == p) continue;
rev[v] = rev[u] + mp[v][u];
dfs(v, u);
h[u] = max(h[v] + mp[v][u], h[u]);
int x = dcu[v];
int y = dcu[u];
if(g[x] + rev[x] > g[y] + rev[y]) dcu[u] = x;
}
int k = adj[u].size();
pre[0] = suf[k + 1] = 0;
for(int i = 1; i <= k; ++i){
int v = adj[u][i - 1];
pre[i] = pre[i - 1];
if(v == p) continue;
if(pre[i] == 0) pre[i] = v;
else{
int x = pre[i];
if(h[x] + mp[x][u] < h[v] + mp[v][u]) pre[i] = v;
}
}
for(int i = k; i >= 1; --i){
int v = adj[u][i - 1];
suf[i] = suf[i + 1];
if(v == p) continue;
if(suf[i] == 0) suf[i] = v;
else{
int x = suf[i];
if(h[x] + mp[x][u] < h[v] + mp[v][u]) suf[i] = v;
}
}
for(int i = 1; i <= k; ++i){
int v = adj[u][i - 1];
if(v == p) continue;
int x = dcu[v];
int y = pre[i - 1];
if(y > 0){
int cost = g[x] + rev[x] - rev[u] + h[y] + mp[y][u];
if(cost > ma){
ma = cost;
S = x;
T = y;
}
}
y = suf[i + 1];
if(y > 0){
int cost = g[x] + rev[x] - rev[u] + h[y] + mp[y][u];
if(cost > ma){
ma = cost;
S = x;
T = y;
}
}
}
}
ll ans[nmax];
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("code.inp", "r", stdin);
// freopen("code.out", "w", stdout);
cin >> n;
sum = 0;
for(int i = 1, u, v, x, y; i < n; ++i){
cin >> u >> v >> x >> y;
adj[u].push_back(v);
adj[v].push_back(u);
mp[u][v] = y;
mp[v][u] = x;
sum += x + y;
a[i] = {u, v, x, y};
}
dfs_1(1, -1);
dfs_2(1, -1);
ans[1] = oo;
for(int i = 1; i <= n; ++i){
ans[1] = min(ans[1], sum - f[i] - g[i]);
}
sort(leaf.begin(), leaf.end(), [](int a, int b){
return f[a] + g[a] > f[b] + g[b];
});
// S = leaf[0];
dfs(1, -1);
memset(h, 0, sizeof h);
// cout <<sum << ' '<< g[4] << ' ' << mp[3][1] << endl;
dfs_3(S, -1);
dfs_4(S, -1);
sort(dp + 1, dp + 1 + nchain, greater<ll>());
for(int i = 2; i <= n; ++i){
sum -= dp[i - 1];
ans[i] = min(ans[i - 1], sum);
}
cin >> q;
while(q--){
int x;
cin >> x;
cout << ans[x] << endl;
}
}
/*
4
1 2 1 2
1 3 3 4
1 4 5 6
2 1 2
*/
Compilation message
designated_cities.cpp:154:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
154 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
15964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
15964 KB |
Output is correct |
| 2 |
Incorrect |
418 ms |
71788 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
15964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
15964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
15964 KB |
Output is correct |
| 2 |
Incorrect |
418 ms |
71788 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
15964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
