#include <bits/stdc++.h>
using namespace std;
#define int long long
struct edge {
int v, c, d;
bool operator == (const edge &b) const {
return (v == b.v && c == b.c && d == b.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;
}
}
int RT;
int fa[maxn], cost[maxn];
int curans;
void dfs2(int u) {
for (auto [v, c, d]:adj[u]) {
curans += d;
edge del = {u, d, c};
adj[v].erase(find(adj[v].begin(), adj[v].end(), del));
fa[v] = u;
cost[v] = cost[u] + c;
dfs2(v);
}
}
void euler(int u, int val) {
cost[u] += val;
for (auto [v, c, d]:adj[u]) euler(v, val);
}
// int curans;
void update(int u) {
vector<int> vec;
while (cost[u]) {
vec.push_back(u);
u = fa[u];
}
reverse(vec.begin(), vec.end());
for (int i:vec) {
curans += cost[i];
euler(i, -cost[i]);
}
}
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});
RT = firsttwo.first;
cost[RT] = 0;
curans = 0;
dfs2(RT);
// update(firsttwo.second);
// curans = ans[2];
for (int i=2;i<=2;i++) {
pair<int,int> mx = {0, 0};
for (int j=1;j<=n;j++) mx = max(make_pair(cost[j], j), mx);
if (mx.first != 0) update(mx.second);
ans[i] = curans;
}
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... |