#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
#define fi first
#define se second
using LL = long long;
int n, q;
LL sumCost = 0;
vector<int> par;
vector<vector<int> > gr, Set;
vector<vector<pair<LL, int> > > mx;
vector<LL> down, up, ans;
vector<pair<int, int> > query;
struct Edge {
int to, cost;
Edge(int _to = 0, int _cost = 0) : to(_to), cost(_cost) {}
};
vector<Edge> edge;
LL calDown(int u, int pr) {
for (int i : gr[u]) {
int v = edge[i].to, cost = edge[i ^ 1].cost;
if (v == pr) continue ;
Set[u].emplace_back(calDown(v, u) + edge[i].cost);
down[u] += down[v] + cost;
}
Set[u].emplace_back(0);
sort(all(Set[u]) );
return Set[u].back();
}
void calUp(int u, int pr) {
for (int i : gr[u]) {
int v = edge[i].to, cost = edge[i ^ 1].cost;
if (v == pr) continue ;
up[v] = up[u] + down[u] - down[v] - cost + edge[i].cost;
calUp(v, u);
}
}
void dfs(int u, int pr) {
for (int i : gr[u]) {
int v = edge[i].to, cost = edge[i].cost;
if (v == pr) continue ;
par[v] = u;
down[v] = down[u] + cost;
up[v] = up[u] + edge[i ^ 1].cost;
dfs(v, u);
mx[u].emplace_back(mx[v].back() );
}
mx[u].emplace_back(down[u], u);
sort(all(mx[u]) );
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("input", "r", stdin);
// freopen("output", "w", stdout);
cin >> n;
gr.assign(n + 5, vector<int>() );
for (int i = 0; i < n - 1; ++i) {
int u, v, c, d; cin >> u >> v >> c >> d;
sumCost += c; sumCost += d;
gr[u].emplace_back(sz(edge) ); edge.emplace_back(v, c);
gr[v].emplace_back(sz(edge) ); edge.emplace_back(u, d);
}
Set.assign(n + 5, {} );
down.assign(n + 5, 0);
up.assign(n + 5, 0);
calDown(1, 1);
calUp(1, 1);
int root = 0;
LL curAns = 0, ans1 = 0;
for (int u = 1; u <= n; ++u) {
LL tmp = down[u] + up[u];
ans1 = max(ans1, tmp);
reverse(all(Set[u]) );
for (int i = 0; i < min(2, sz(Set[u]) ); ++i) tmp += Set[u][i];
if (tmp > curAns) {
root = u;
curAns = tmp;
}
}
cin >> q;
query.reserve(q);
ans.assign(q, 0);
for (int i = 0; i < q; ++i) {
int e; cin >> e;
if (e == 1) ans[i] = ans1;
else query.emplace_back(e, i);
}
sort(query.begin(), query.end() );
par.assign(n + 5, 0);
mx.assign(n + 5, {} );
down[root] = up[root] = 0; dfs(root, root);
// cerr << "root = " << root << '\n';
priority_queue<pair<LL, int> > pq;
int nMark = 0;
while (nMark < 2) {
int u = mx[root].back().se;
// cerr << "u = " << u << " cost = " << cost << '\n';
while (u) {
// cerr << u << "\n";
int pr = par[u];
par[u] = 0;
mx[u].pop_back();
u = pr;
}
// for (u = 1; u <= n; ++u) {
// cerr << "u = " << u << ' ';
// for (auto _ : mx[u]) cerr << _.se << ' ';
// cerr << '\n';
// }
++nMark;
}
for (int u = 1; u <= n; ++u) if (!par[u]) {
if (sz(mx[u]) ) {
pq.emplace(mx[u].back().fi - down[u], mx[u].back().se);
// cerr << mx[u].back().se << "???\n";
}
}
for (auto que : query) {
int e = que.fi, id = que.se;
// cerr << "id = " << id << '\n';
while (nMark < e) {
assert(sz(pq) );
int u = pq.top().se;
LL cost = pq.top().fi;
pq.pop();
curAns += cost;
// cerr << "u = " << u << ' ' << cost << '\n';
while (u) {
// cerr << u << ' ' << par[u] << '\n';
int pr = par[u];
par[u] = 0;
mx[u].pop_back();
if (sz(mx[u]) ) {
pq.emplace(mx[u].back().fi - down[u], mx[u].back().se);
}
u = pr;
}
// for (u = 1; u <= n; ++u) {
// cerr << "u = " << u << '\n';
// for (auto _ : mx[u]) cerr << _.se << ' ';
// cerr << '\n';
// }
++nMark;
}
ans[id] = curAns;
}
for (int i = 0; i < q; ++i) cout << sumCost - ans[i] << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
575 ms |
44504 KB |
Output is correct |
| 3 |
Correct |
750 ms |
72672 KB |
Output is correct |
| 4 |
Correct |
560 ms |
44512 KB |
Output is correct |
| 5 |
Correct |
598 ms |
44512 KB |
Output is correct |
| 6 |
Correct |
716 ms |
48352 KB |
Output is correct |
| 7 |
Correct |
523 ms |
44620 KB |
Output is correct |
| 8 |
Correct |
931 ms |
73300 KB |
Output is correct |
| 9 |
Correct |
512 ms |
45132 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
713 ms |
44740 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
575 ms |
44504 KB |
Output is correct |
| 3 |
Correct |
750 ms |
72672 KB |
Output is correct |
| 4 |
Correct |
560 ms |
44512 KB |
Output is correct |
| 5 |
Correct |
598 ms |
44512 KB |
Output is correct |
| 6 |
Correct |
716 ms |
48352 KB |
Output is correct |
| 7 |
Correct |
523 ms |
44620 KB |
Output is correct |
| 8 |
Correct |
931 ms |
73300 KB |
Output is correct |
| 9 |
Correct |
512 ms |
45132 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Incorrect |
713 ms |
44740 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
