#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;
int par[nmax];
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];
par[v] = u;
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];
}
for(auto v: adj[u]){
if(v == p) continue;
dfs_2(v, u);
}
}
ll sum = 0;
int h[nmax], one[nmax];
ll dp[nmax], nchain = 1;
void dfs_3(int u, int p){
h[u] = 0;
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], two[nmax];
void dfs(int u, int p){
dcu[u] = h[u] = u;
for(auto v : adj[u]){
if(v == p) continue;
rev[v] = rev[u] + mp[v][u];
two[v] = two[u] + mp[u][v];
dfs(v, u);
int x = dcu[v];
int y = dcu[u];
if(g[x] + rev[x] > g[y] + rev[y]) dcu[u] = x;
x = h[u];
y = h[v];
if(rev[x] < rev[y]) h[u] = y;
}
for(auto v : adj[u]){
if(v == p) continue;
// cout << dcu[v] << ' ';
}
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] = h[v];
else{
int x = pre[i];
if(rev[x] < rev[h[v]]) pre[i] = h[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] = h[v];
else{
int x = suf[i];
if(rev[x] < rev[h[v]]) suf[i] = h[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] + two[x] - two[u] + rev[y] -rev[u];
if(cost > ma){
ma = cost;
S = x;
T = y;
}
}
y = suf[i + 1];
if(y > 0){
int cost = g[x] + two[x] - two[u] + rev[y] -rev[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 = 1, T = leaf[0], ma = g[T];
int x = T;
while(x > 1){
ma += mp[par[x]][x];
x = par[x];
}
dfs(1, -1);
dfs_3(S, -1);
dfs_4(S, -1);
sort(dp + 1, dp + 1 + nchain, greater<ll>());
ans[2] = ma;
for(int i = 3; i <= n; ++i){
ans[i] = ans[i - 1] + dp[i - 1];
}
cin >> q;
while(q--){
int x;
cin >> x;
cout << ans[x] << endl;
}
}
/*
5
2 4 8 4
3 4 2 2
1 2 7 6
5 4 10 10
1
2
*/
Compilation message
designated_cities.cpp:167:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
167 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
14428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14424 KB |
Output is correct |
| 2 |
Correct |
511 ms |
74944 KB |
Output is correct |
| 3 |
Correct |
549 ms |
95316 KB |
Output is correct |
| 4 |
Correct |
469 ms |
73520 KB |
Output is correct |
| 5 |
Correct |
556 ms |
75520 KB |
Output is correct |
| 6 |
Correct |
541 ms |
77904 KB |
Output is correct |
| 7 |
Correct |
793 ms |
77544 KB |
Output is correct |
| 8 |
Correct |
579 ms |
96332 KB |
Output is correct |
| 9 |
Correct |
958 ms |
78936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
14424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
14428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14424 KB |
Output is correct |
| 2 |
Correct |
511 ms |
74944 KB |
Output is correct |
| 3 |
Correct |
549 ms |
95316 KB |
Output is correct |
| 4 |
Correct |
469 ms |
73520 KB |
Output is correct |
| 5 |
Correct |
556 ms |
75520 KB |
Output is correct |
| 6 |
Correct |
541 ms |
77904 KB |
Output is correct |
| 7 |
Correct |
793 ms |
77544 KB |
Output is correct |
| 8 |
Correct |
579 ms |
96332 KB |
Output is correct |
| 9 |
Correct |
958 ms |
78936 KB |
Output is correct |
| 10 |
Incorrect |
7 ms |
14424 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
14428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
