Submission #511669

#	Time	Username	Problem	Language	Result	Execution time	Memory
511669		Monarchuwu	Chase (CEOI17_chase)	C++17	70 / 100	3533 ms	90764 KiB

chase

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;

#include<chrono>
#include<random>
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e5 + 9, K = 100 + 2;
int n, V;
int p[N];
vector<int> g[N];

ll dp[N][K], ans;
void dfs(int u, int par) {
    for (int j = 1; j <= V; ++j)
        ans = max(ans, dp[u][j]);
    ll s(0);
    for (int v : g[u])
        if (v != par) s += p[v];

    for (int v : g[u]) if (v != par) {
        dp[v][0] = 0;
        for (int j = 1; j <= V; ++j) {
            dp[v][j] = max(dp[u][j], dp[u][j - 1] + s);
        }
        dfs(v, u);
    }
}
void calc(int u) {
    fill(dp[u], dp[u] + V + 1, 0);
    dfs(u, 0);
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> V;
    for (int i = 1; i <= n; ++i) cin >> p[i];
    for (int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    if (n <= 1000) {
        for (int i = 1; i <= n; ++i) calc(i);
    }
    else {
        calc(1);
        for (int i = 0; i < 70; ++i)
            calc(rd() % (n - 1) + 2);
    }
    cout << ans << '\n';
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/
/*
==================================================+
INPUT:                                            |
--------------------------------------------------|
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
--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|
36
--------------------------------------------------|
==================================================+
*/

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