Submission #468634

#	Time	Username	Problem	Language	Result	Execution time	Memory
468634		idk321	Chase (CEOI17_chase)	C++17	0 / 100	246 ms	524292 KiB

chase

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 100005;
const int V = 101;
int p[N];
int n, v;
vector<int> adj[N];


struct comp {
    bool operator () (const array<ll,2>& ar1, const array<ll,2>& ar2) const {
        return ar1 > ar2;
    }
};

bool comp_fn (const array<ll,2>& ar1, const array<ll,2>& ar2)  {
    return ar1 > ar2;
}


struct SetLike {
    array<array<ll, 2>, 2> v;
    int len = 0;

    array<array<ll, 2>, 2>::iterator begin() {
        return v.begin();
    }
    array<array<ll, 2>, 2>::iterator end() {
        return v.begin() + len;
    }
    array<array<ll, 2>, 2>::iterator erase(array<array<ll, 2>, 2>::iterator it) {
        len--;
        if (it == v.begin()) {
            swap(v[0], v[1]);
            return v.begin();
        }

        return v.begin() + 1;
    }

    void insert(array<ll, 2> ar) {
        if (len < 2) {
            v[len] = ar;
            len++;
        } else {
            if (ar > v[1]) swap(ar, v[1]);
            if (v[1] > v[0]) swap(v[0], v[1]);
        }
    }
};
SetLike dp[N][2][V];


void dfs(int node, int par) {

    ll val1 = 0;
    for (int next : adj[node]) {
        if (next == par) continue;
        val1 += p[next];
        dfs(next, node);
    }

    dp[node][1][1].insert({val1, node});
    for (int next : adj[node]) {
        if (next == par) continue;
        for (int i = 0; i <= v; i++) {
            dp[node][0][i].insert({max((*dp[next][0][i].begin())[0], (*dp[next][1][i].begin())[0]), next});
            if (i != v) dp[node][1][i + 1].insert({max(val1 + (*dp[next][0][i].begin())[0], val1 + (*dp[next][1][i].begin())[0]), next});
        }
    }

    for (int i = 0; i <= v; i++) {
        for (int j = 0; j < 2; j++) dp[node][j][i].insert({0, node});
    }
}

void transferRoot(int first, int second) {
    ll defaultValue = 0;
    for (int next : adj[second]) {
        if (next == first) continue;
        defaultValue += p[next];
    }


    for (int i = 0; i <= v; i++) {
        auto it0 = dp[first][0][i].begin();
        auto it1 = dp[first][1][i].begin();
        if ((*it0)[1] == second) it0++;
        if ((*it1)[1] == second) it1++;
        ll val0 = 0;
        ll val1 = 0;
        if (it0 != dp[first][0][i].end()) val0 = (*it0)[0];
        if (it1 != dp[first][1][i].end()) val1 = (*it1)[0];
        dp[second][0][i].insert({max(val0, val1 - p[second]), first});
        if (i != v) dp[second][1][i + 1].insert({max(val0 + defaultValue, val1 - p[second] + defaultValue), first});
    }

    for (int i = 1; i <= v; i++) {

        auto it = dp[second][1][i].begin();
        array<ll, 2> newEl = {(*it)[0] + p[first], (*it)[1]};
        it = dp[second][1][i].erase(it);
        if (it != dp[second][1][i].end()) {
            array<ll, 2> newEl2 = {(*it)[0] + p[first], (*it)[1]};

            dp[second][1][i].erase(it);
            dp[second][1][i].insert(newEl2);
        }
        dp[second][1][i].insert(newEl);
    }
}

ll result = 0;

void dfsRoot(int node, int par) {
    for (int i = 0; i <= v; i++) {
        for (int j = 0; j < 2; j++) {
            result = max(result, (*dp[node][j][i].begin())[0]);
        }
    }
    cout << node << " " << result << endl;

    for (int next : adj[node]) {
        if (next == par) continue;
        transferRoot(node, next);
        dfsRoot(next, node);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> v;
    for (int i = 1; i <= n; i++) cin >> p[i];
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    dfs(1, -1);
    dfsRoot(1, -1);
    cout << result << "\n";
}

/*
12 2
2 3 3 8 1 5 6 7 8 3 5 4
2 1
2 7
3 4
4 7
7 6
5 6
6 8
6 9
7 10
10 11
10 12
*/

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30