Submission #1255387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255387		thdh__	Designated Cities (JOI19_designated_cities)	C++20	100 / 100	235 ms	59152 KiB

designated_cities

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define bruh ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int ll

using namespace std;
typedef pair<int,int> pii;
const int N = 2e5+5;
const int inf = (int)1e18;

int n,q;
vector<pair<int, pii>> adj[N];
vector<int> delta[N];
int best[N];
long long ans[N];
long long sum_global;
long long mn_global, add_global;
int root;

long long dfs(int u, int p, long long cur) {
    long long mx1 = -inf, mx2 = -inf;
    for (auto &e : adj[u]) {
        int v = e.fi, a = e.se.fi, b = e.se.se;
        if (v == p) continue;
        sum_global += a;
        long long tmp = dfs(v, u, cur + b - a) + a;
        if (mx1 < tmp) { mx2 = mx1; mx1 = tmp; }
        else if (mx2 < tmp) mx2 = tmp;
    }
    add_global = min(add_global, cur);
    if (mn_global > cur - mx1 - mx2 && adj[u].size() != 1) {
        mn_global = cur - mx1 - mx2;
        root = u;
    }
    return max(mx1, 0ll);
}

void dfs1(int u, int p) {
    int heavy = -1;
    int id1 = -1, id2 = -1;
    long long mx1 = -inf, mx2 = -inf;
    int mxsz = 0;
    for (auto &e : adj[u]) {
        int v = e.fi, a = e.se.fi, b = e.se.se;
        if (v == p) continue;
        sum_global += a;
        dfs1(v, u);
        best[v] += a;
        if ((int)delta[v].size() > mxsz) { mxsz = (int)delta[v].size(); heavy = v; }
        if (best[v] > mx1) {
            mx2 = mx1; id2 = id1;
            mx1 = best[v]; id1 = v;
        } else if (best[v] > mx2) {
            mx2 = best[v]; id2 = v;
        }
    }
    if (heavy != -1) delta[u].swap(delta[heavy]);
    for (auto &e : adj[u]) {
        int v = e.fi, a = e.se.fi, b = e.se.se;
        if (v == p) continue;
        if (v != heavy) {
            for (int val : delta[v]) delta[u].pb(val);
        }
        if (v != id1 && (p != 0 || v != id2)) delta[u].pb(best[v]);
    }
    if (mx1 == -inf) best[u] = 0;
    else best[u] = (int)mx1;
    if (p == 0 && mx2 != -inf) best[u] = (int)(mx1 + mx2);
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        adj[i].clear();
        delta[i].clear();
        best[i] = 0;
        ans[i] = 0;
    }
    sum_global = 0;
    mn_global = inf;
    add_global = inf;
    root = 1;

    for (int i = 1; i < n; ++i) {
        int u,v,a,b; cin >> u >> v >> a >> b;
        adj[u].pb({v,{a,b}});
        adj[v].pb({u,{b,a}});
    }
    for (int i = 1; i <= n; ++i) if (adj[i].size() > 1) { root = i; break; }
    dfs(root, 0, 0);
    ans[0] = sum_global + add_global;
    sum_global = 0;
    dfs1(root, 0);
    ans[1] = sum_global - best[root];
    sort(all(delta[root]));
    int sz = (int)delta[root].size();
    for (int k = 2; k <= n-1; ++k) {
        if (!delta[root].empty()) {
            ans[k] = ans[k-1] - (long long)delta[root].back();
            delta[root].pop_back();
        } else ans[k] = ans[k-1];
    }

    cin >> q;
    while (q--) {
        int x; cin >> x;
        cout << ans[x-1] << "\n";
    }
}

signed main() {
    bruh
    solve();
    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 44 / 44