#include <bits/stdc++.h>
using namespace std;
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 2e5+10, MOD = 1e9+7;
const ll INF = 1e18+10;
int n;
vector<ar<int, 3>> adj[N];
ll ans[N];
ll calc_one(int c, int p) {
ll sum = 0;
for (auto [nxt, w, _] : adj[c]) if (nxt != p) {
sum += w + calc_one(nxt, c);
}
return sum;
}
void dfs1(int c, int p, ll x) {
ans[1] = min(ans[1], x);
for (auto [nxt, a, b] : adj[c]) if (nxt != p) {
dfs1(nxt, c, x - a + b);
}
}
int sub[N];
bool blocked[N];
int dfs_sub(int c, int p) {
sub[c] = 1;
for (auto [nxt, x, y] : adj[c]) if (nxt != p && !blocked[nxt]) {
sub[c] += dfs_sub(nxt, c);
}
return sub[c];
}
int dfs_cent(int c, int p, int cnt) {
for (auto [nxt, x, y] : adj[c]) if (nxt != p && !blocked[nxt] && sub[nxt] > cnt / 2)
return dfs_cent(nxt, c, cnt);
return c;
}
pair<ll, int> dfs_best(int c, int p, ll x) {
pair<ll, int> best{x, c};
for (auto [nxt, w, _] : adj[c]) if (!blocked[nxt] && nxt != p) {
best = max(best, dfs_best(nxt, c, x + w));
}
return best;
}
vector<int> roots;
int process(int c) {
roots.push_back(c); // can't hurt, and probably useful
ll best_w = -1;
int best_nxt = -1, best_c = -1;
for (auto [nxt, w, _] : adj[c]) if (!blocked[nxt]) {
auto cur = dfs_best(nxt, c, w);
if (cur.first > best_w) {
best_w = cur.first;
best_nxt = nxt;
best_c = cur.second;
}
}
if (best_c != -1) {
roots.push_back(best_c);
}
return best_nxt;
}
void build(int c) {
if (c == -1) return;
int cnt = dfs_sub(c, -1);
int cent = dfs_cent(c, -1, cnt);
int nxt = process(cent);
blocked[cent] = 1;
build(nxt);
}
int par[N], par_w[N], st[N], en[N], et[N], tt;
ll sum[N];
bool marked[N];
ll lzy[4 * N];
pair<ll, int> t[4 * N];
void build(int v, int tl, int tr) {
if (tl == tr) t[v] = {sum[tl], tl};
else {
int tm = (tl + tr) / 2;
build(2*v, tl, tm), build(2*v+1, tm+1, tr);
t[v] = max(t[2*v], t[2*v+1]);
}
}
void push(int v, int tl, int tr, ll x) {
if (!x) return;
t[v].first += x;
if (tl != tr)
lzy[2*v] += x, lzy[2*v+1] += x;
}
void app(int v, int tl, int tr) {
push(v, tl, tr, lzy[v]);
lzy[v] = 0;
}
void upd(int v, int tl, int tr, int l, int r, ll x) {
app(v, tl, tr);
if (r < tl || l > tr) return;
if (l <= tl && tr <= r) {
push(v, tl, tr, x);
return;
}
int tm = (tl + tr) / 2;
upd(2*v, tl, tm, l, r, x), upd(2*v+1, tm+1, tr, l, r, x);
t[v] = max(t[2*v], t[2*v+1]);
}
pair<ll, int> qry(int v, int tl, int tr, int l, int r) {
app(v, tl, tr);
if (r < tl || l > tr) return {-INF, -1};
if (l <= tl && tr <= r) return t[v];
int tm = (tl + tr) / 2;
return max(qry(2*v, tl, tm, l, r), qry(2*v+1, tm+1, tr, l, r));
}
void dfs_root(int c, int p) {
par[c] = p;
et[st[c] = tt++] = c;
for (auto [nxt, w, _] : adj[c]) if (nxt != p) {
par_w[nxt] = w;
dfs_root(nxt, c);
}
en[c] = tt-1;
}
void add(int root) {
tt = 0;
memset(par, -1, sizeof(par));
memset(sum, 0, sizeof(sum));
memset(par_w, 0, sizeof(par_w));
dfs_root(root, -1);
for (int i = 1; i < n; i++) {
int c = et[i];
sum[i] = sum[st[par[c]]] + par_w[c];
}
memset(marked, 0, sizeof(marked));
ll cur = accumulate(par_w, par_w + n, 0LL);
build(1, 0, n-1);
for (int i = 1; i <= n; i++) {
/*
pair<ll, int> best{-1, -1};
for (int c = 0; c < n; c++) best = max(best, {sum[c], c});
*/
pair<ll, int> best = qry(1, 0, n-1, 0, n-1);
int c = et[best.second];
while (c != -1 && !marked[c]) {
marked[c] = 1;
upd(1, 0, n-1, st[c], en[c], -par_w[c]);
// for (int j = st[c]; j <= en[c]; j++) sum[j] -= par_w[c];
cur -= par_w[c];
c = par[c];
}
ans[i+1] = min(ans[i+1], cur);
}
}
void solve() {
cin >> n;
for (int i = 0; i < n-1; i++) {
int a, b; cin >> a >> b, --a, --b;
int x, y; cin >> x >> y;
adj[a].push_back({b, x, y});
adj[b].push_back({a, y, x});
}
fill(ans, ans + n, INF);
dfs1(0, -1, calc_one(0, -1));
build(0);
for (int c : roots) add(c);
int q; cin >> q;
while (q--) {
int x; cin >> x;
cout << ans[x] << '\n';
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int T = 1;
// cin >> T;
while (T--) solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8276 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8276 KB |
Output is correct |
| 3 |
Correct |
5 ms |
8276 KB |
Output is correct |
| 4 |
Correct |
4 ms |
8276 KB |
Output is correct |
| 5 |
Correct |
4 ms |
8276 KB |
Output is correct |
| 6 |
Incorrect |
4 ms |
8276 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8276 KB |
Output is correct |
| 2 |
Execution timed out |
2066 ms |
34612 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8276 KB |
Output is correct |
| 2 |
Execution timed out |
2045 ms |
34600 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8276 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8276 KB |
Output is correct |
| 3 |
Correct |
5 ms |
8276 KB |
Output is correct |
| 4 |
Correct |
4 ms |
8276 KB |
Output is correct |
| 5 |
Correct |
4 ms |
8276 KB |
Output is correct |
| 6 |
Incorrect |
4 ms |
8276 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8276 KB |
Output is correct |
| 2 |
Execution timed out |
2066 ms |
34612 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8276 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8276 KB |
Output is correct |
| 3 |
Correct |
5 ms |
8276 KB |
Output is correct |
| 4 |
Correct |
4 ms |
8276 KB |
Output is correct |
| 5 |
Correct |
4 ms |
8276 KB |
Output is correct |
| 6 |
Incorrect |
4 ms |
8276 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
