#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmax(a, b) a = max(a, b)
#define chkmin(a, b) a = min(a, b)
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;
const int MAX_N = 2e5 + 5;
ll ans[MAX_N];
bool visited[MAX_N];
int sz[MAX_N];
vii tree[MAX_N];
int DfsSz(int node, int par) {
sz[node] = 1;
for (auto [neighbor, w] : tree[node]) {
if (neighbor != par && !visited[neighbor]) sz[node] += DfsSz(neighbor, node);
}
return sz[node];
}
int FindCentroid(int node) {
DfsSz(node, node);
int s = sz[node];
int par = node;
while (true) {
bool ok = true;
for (auto [neighbor, w] : tree[node]) {
if (!visited[neighbor] && neighbor != par && sz[neighbor] >= s / 2) {
par = node;
node = neighbor;
ok = false;
break;
}
}
if (ok) break;
}
return node;
}
vii options;
ll Solve(int node, int par, ll d, int ind) {
vi v = {0};
for (auto [neighbor, w] : tree[node]) {
if (neighbor != par && !visited[neighbor]) {
v.push_back(Solve(neighbor, node, w, ind));
}
}
int i = max_element(all(v)) - v.begin();
swap(v[0], v[i]);
for (int j = 1; j < v.size(); j++) {
options.push_back({v[j], ind});
}
return v[0] + d;
}
ll CalcBonus(int node, int par) {
ll s = 0;
for (auto [neighbor, w] : tree[node]) {
if (neighbor == par) s += w;
else if (!visited[neighbor]) s += CalcBonus(neighbor, node);
}
return s;
}
void CentroidDecomposition(int node, ll bonus) {
int centroid = FindCentroid(node);
options.clear();
for (auto [node, w] : tree[centroid]) {
if (!visited[node]) {
options.push_back({Solve(node, centroid, w, node), node});
}
}
options.push_back({0, centroid});
ll curr = CalcBonus(centroid, centroid) + bonus;
sort(all(options), greater<pii>());
chkmax(ans[1], curr);
if (options.size() == 1) return;
ll s = curr + options[0].x;
int i = 1;
while (options[i].y == options[0].y) i++;
s += options[i].x;
chkmax(ans[2], s);
for (int j = 1, c = 2; j < options.size(); j++) {
if (j != i) c++, s += options[j].x;
chkmax(ans[c], s);
}
visited[centroid] = true;
for (auto [node, w] : tree[centroid]) {
if (!visited[node]) {
CentroidDecomposition(node, curr + w - CalcBonus(node, centroid));
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
ll s = 0;
for (int i = 0; i < n - 1; i++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
s += c + d;
tree[a].push_back({b, c});
tree[b].push_back({a, d});
}
CentroidDecomposition(1, 0);
int q;
cin >> q;
while (q--) {
int e;
cin >> e;
cout << s - ans[e] << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |