Submission #1350292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1350292		rmielamud	Designated Cities (JOI19_designated_cities)	C++20	In queue	0 ms	0 KiB

designated_cities

#include <bits/stdc++.h>

using namespace std;

#define short int32_t
#define int int64_t
#define long __int128_t

const int inf{numeric_limits<int>::max() / 4};

struct Edge {
    int to, w, w_rev;
};

struct SegmentTree {
    int size{};
    vector<int> added{};
    vector<pair<int, int>> maxs{};

    SegmentTree(int size) : size(size) {
        added.assign(size * 4, 0);
        maxs.resize(size * 4);
        _build(1, 0, size);
    }

    void _build(int node, int low, int high) {
        maxs[node] = {0, low};

        if (low == high - 1) {
            return;
        }

        int mid{(low + high) / 2};

        _build(node * 2, low, mid);
        _build(node * 2 + 1, mid, high);
    }

    void add(int low, int high, int val) {
        _add(1, 0, size, low, high, val);
    }

    void _add(int node, int low, int high, int qlow, int qhigh, int val) {
        if (qlow >= high || qhigh <= low) {
            return;
        }

        if (qlow <= low && qhigh >= high) {
            added[node] += val;
            maxs[node].first += val;
            return;
        }

        int mid{(low + high) / 2};

        _add(node * 2, low, mid, qlow, qhigh, val);
        _add(node * 2 + 1, mid, high, qlow, qhigh, val);

        maxs[node] = max(maxs[node * 2], maxs[node * 2 + 1]);
        maxs[node].first += added[node];
    }

    pair<int, int> get_max(int low, int high) {
        return _get_max(1, 0, size, low, high);
    }

    pair<int, int> _get_max(int node, int low, int high, int qlow, int qhigh) {
        if (qlow >= high || qhigh <= low) {
            return {-inf, 0};
        }

        if (qlow <= low && qhigh >= high) {
            return maxs[node];
        }

        int mid{(low + high) / 2};

        pair<int, int> res{max(
            _get_max(node * 2, low, mid, qlow, qhigh),
            _get_max(node * 2 + 1, mid, high, qlow, qhigh)
        )};

        res.first += added[node];

        return res;
    }
};

short main() {
    #ifndef LOCAL
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
    #endif

    int n;
    cin >> n;

    vector<vector<Edge>> edges(n);
    int total_w{0};

    for (int i{0}; i < n - 1; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;

        a--;
        b--;

        edges[a].push_back({b, c, d});
        edges[b].push_back({a, d, c});
        total_w += c + d;
    }

    vector<int> w_up(n);
    vector<int> tin(n);
    vector<int> order(n);
    vector<int> tout(n);
    vector<int> parents(n);
    vector<Edge> parent_edges(n);
    int timer{0};

    function<void(int, int)> dfs1 = [&](int node, int parent) {
        tin[node] = timer++;
        order[tin[node]] = node;
        parents[node] = parent;

        for (auto [to, w, w_rev] : edges[node]) {
            if (to != parent) {
                dfs1(to, node);
                w_up[tin[node]] += w_up[tin[to]] + w_rev;
            } else {
                parent_edges[node] = {to, w, w_rev};
            }
        }

        tout[node] = timer;
    };

    dfs1(0, -1);

    int best_center{0};

    vector<int> w_in(n);
    SegmentTree st(n);

    function<void(int, int, int)> dfs2 = [&](int node, int w_root, int _w_down) {
        st.add(tin[node], tin[node] + 1, w_root);
        w_in[tin[node]] = w_up[tin[node]] + _w_down;
        best_center = max(best_center, w_in[tin[node]]);

        for (auto [to, w, w_rev] : edges[node]) {
            if (to != parents[node]) {
                dfs2(to, w_root + w, _w_down + w + w_up[tin[node]] - w_up[tin[to]] - w_rev);
            }
        }
    };

    dfs2(0, 0, 0);
    int best_dia_w{-1};
    int best_dia1{};
    int best_dia2{};

    function<void(int)> dfs3 = [&](int node) {
        auto [max_w, max]{st.get_max(0, n)};
        max_w += w_in[tin[node]];

        if (max_w > best_dia_w) {
            best_dia_w = max_w;
            best_dia1 = node;
            best_dia2 = order[max];
        }

        for (auto [to, w, w_rev] : edges[node]) {
            if (to != parents[node]) {
                st.add(0, n, w_rev);
                st.add(tin[to], tout[to], -w - w_rev);
                dfs3(to);
                st.add(tin[to], tout[to], w + w_rev);
                st.add(0, n, -w_rev);
            }
        }
    };

    dfs3(0);

    vector<int> anss(n + 1);
    anss[1] = best_center;
    anss[2] = best_dia_w;

    st = SegmentTree(n);
    timer = 0;
    w_up.assign(n, 0);
    w_in.assign(n, 0);
    dfs1(best_dia1, -1);
    dfs2(best_dia1, 0, 0);

    vector<bool> between_selected(n);
    between_selected[best_dia1] = true;

    auto mark_path = [&](int node) {
        while (!between_selected[node]) {
            between_selected[node] = true;
            st.add(tin[node], tout[node], -parent_edges[node].w_rev);
            node = parents[node];
        }
    };

    mark_path(best_dia2);

    for (int i{3}; i <= n; i++) {
        auto [max_w, max]{st.get_max(0, n)};
        anss[i] = anss[i - 1] + max_w;
        mark_path(order[max]);
    }

    int q;
    cin >> q;

    for (int i{0}; i < q; i++) {
        int e;
        cin >> e;
        cout << total_w - anss[e] << "\n";
    }

    return 0;
}