Submission #698370

#	Time	Username	Problem	Language	Result	Execution time	Memory
698370		sugartheanh	Chase (CEOI17_chase)	C++14	30 / 100	222 ms	156428 KiB

chase

#include <bits/stdc++.h>
 
            using namespace std;
            using ll = long long;
 
            #define int ll
 
            int res, N, K, P[100005];
            int X[100001][101], Y[100001][101];
            vector<int> adj[100005];
 
            void dfs(int v, int p) {
                int S = 0;
                for(auto u : adj[v]) S += P[u];
                X[v][1] = S;
                for(auto u : adj[v]) {
                    if(u == p) continue;
                    dfs(u, v);
                    for(int i = 1; i <= K; i++) {
                        res = max(res, X[v][i] + Y[u][K - i]);
                        X[v][i] = max({X[v][i], X[v][i - 1], X[u][i], X[u][i - 1] + S - P[u]});
                        Y[v][i] = max({Y[v][i], Y[v][i - 1], Y[u][i], Y[u][i - 1] + S - P[p]});
                    }
                }
 
               
            }
 
            int32_t main() {
                ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                cin >> N >> K;
                for(int l = 1; l <= N; l++)
                    cin >> P[l];
                for(int l = 0; l < N - 1; l++) {
                    int U, V; cin >> U >> V;
                    adj[U].push_back(V);
                    adj[V].push_back(U);
                }
                dfs(1, 0);
                cout << res << "\n";
                return 0;
            }

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