#include <bits/stdc++.h>
using namespace std;
#define int long long
struct edge {
int v, c, d;
};
const int maxn = 2e5 + 5;
int n;
vector<edge> adj[maxn];
int ans[maxn];
pair<int,int> mxup[maxn];
int cur = 0;
void dfs0(int u, int f) {
mxup[u] = {0, u};
for (auto [v, c, d]:adj[u]) if (v != f) {
dfs0(v, u);
pair<int,int> val = mxup[v];
val.first += c;
mxup[u] = max(val, mxup[u]);
cur += d;
}
}
pair<int,int> firsttwo;
void dfs1(int u, int f, pair<int,int> mxdown) {
ans[1] = max(cur, ans[1]);
int curans2 = cur + max(mxdown, mxup[u]).first;
// cout << u << " " << max(mxdown, mxup[u]).second << " " << cur << " " << max(mxdown, mxup[u]).first << " " << curans2 << endl;
// cout << mxup[u].first << " " << mxup[u].second << endl;
if (curans2 > ans[2]) {
ans[2] = curans2;
firsttwo = {u, max(mxdown, mxup[u]).second};
}
vector<pair<int,int>> vec;
for (auto[ v, c, d]:adj[u]) if (v != f) {
pair<int,int> val = mxup[v];
val.first += c;
vec.push_back(val);
}
sort(vec.rbegin(), vec.rend());
for (auto [v, c, d]:adj[u]) if (v != f) {
cur -= d, cur += c;
pair<int,int> nxt = mxdown;
if (adj[u].size() > 1) {
if (vec[0].second != mxup[v].second) nxt = max(vec[0], nxt);
else nxt = max(vec[1], nxt);
}
nxt.first += d;
dfs1(v, u, nxt);
cur += d, cur -= c;
}
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
int all = 0;
for (int i=1;i<=n-1;i++) {
int u, v, c, d;
cin >> u >> v >> c >> d;
adj[u].push_back({v, c, d});
adj[v].push_back({u, d, c});
all += c + d;
}
dfs0(1, 0);
dfs1(1, 0, {0, -1});
int q;
cin >> q;
while (q--) {
int x;
cin >> x;
cout << all - ans[x] << "\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... |