#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;
struct Edge {
int v, a, b;
Edge() {}
Edge(int v_, int a_, int b_) : v(v_), a(a_), b(b_) {}
};
int n;
vector<Edge> e[N];
bool used[N];
int sz[N];
long long ans[N];
void dfs(int u, int p = -1) {
sz[u] = 1;
for (auto [v, a, b] : e[u]) {
if (!used[v] && v != p) {
dfs(v, u);
sz[u] += sz[v];
}
}
}
int centroid(int u, int all, int p = -1) {
for (auto [v, a, b] : e[u]) {
if (!used[v] && v != p && 2 * sz[v] > all) {
return centroid(v, all, u);
}
}
return u;
}
long long zhfs(int u, int p = -1) {
long long res = 0;
for (auto [v, a, b] : e[u]) {
if (!used[v] && v != p) {
res += zhfs(v, u);
res += b;
}
}
return res;
}
long long go(int u, int t, vector<pair<long long, int>> &d, int p = -1) {
vector<long long> cur;
for (auto [v, a, b] : e[u]) {
if (!used[v] && v != p) {
cur.push_back(go(v, t, d, u) + a);
}
}
if (cur.empty()) return 0;
swap(cur[0], cur[max_element(begin(cur), end(cur)) - begin(cur)]);
for (int i = 1; i < (int)cur.size(); ++i) {
d.emplace_back(cur[i], t);
}
return cur[0];
}
void solve(int u, long long bonus) {
dfs(u);
vector<pair<long long, int>> ch;
ch.reserve(e[u].size());
for (auto [v, a, b] : e[u]) {
if (!used[v]) {
long long z = zhfs(v, u);
bonus += b;
bonus += z;
ch.emplace_back(a - z - b, v);
}
}
used[u] = true;
{
vector<pair<long long, int>> d;
d.reserve(sz[u]);
for (auto [v, a, b] : e[u]) {
if (!used[v]) d.emplace_back(go(v, v, d) + a, v);
}
sort(rbegin(d), rend(d));
int f = -1;
for (int i = 1; i < (int)d.size(); ++i) {
if (d[i].second != d[0].second) {
f = i;
break;
}
}
if (f != -1) {
long long cur = 0;
for (int i = 0; i < (int)d.size(); ++i) {
cur += d[i].first;
ans[i + 1 + (i < f)] = max(ans[i + 1 + (i < f)], cur + (i < f ? d[f].first : 0) + bonus);
}
}
}
for (auto [delta, v] : ch) {
bonus += delta;
solve(centroid(v, sz[v]), bonus);
bonus -= delta;
}
}
int main() {
scanf("%d", &n);
long long sum = 0;
for (int i = 0; i < n - 1; ++i) {
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
--a, --b;
e[a].emplace_back(b, c, d);
e[b].emplace_back(a, d, c);
sum += c;
sum += d;
}
dfs(0);
solve(centroid(0, n), 0);
for (int i = 1; i <= n; ++i) {
ans[i] = sum - ans[i];
}
for (int i = 2; i <= n; ++i) {
ans[i] = min(ans[i], ans[i - 1]);
}
int q;
scanf("%d", &q);
while (q--) {
int x;
scanf("%d", &x);
cout << ans[x] << "\n";
}
return 0;
}
Compilation message
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:109:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
109 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
designated_cities.cpp:113:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
113 | scanf("%d%d%d%d", &a, &b, &c, &d);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:129:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
129 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
designated_cities.cpp:132:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
132 | scanf("%d", &x);
| ~~~~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
4992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
4992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
4992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
