oj.uz

Submission #714132

# Submission time Handle Problem Language Result Execution time Memory
714132 2023-03-24T02:28:09 Z Astrayt Chase (CEOI17_chase) C++17
0 / 100
 229 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define pii pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair

int k, ans = 0, p[100005];
ll S[100005];
vector<int> adj[100005];
pii dp1[100005][105][2], dp2[100005][105][2];

void dfs(int u, int par = 0){
	for(auto v:adj[u]){
		if(v == par) continue;
		dfs(v, u);
		for(int i = 1; i <= k; ++i){
			pii p1 = mp(max(dp1[v][i][0].ff, dp1[v][i - 1][0].ff + S[v] - p[u]), v);
			pii p2 = mp(max(dp2[v][i][0].ff, dp2[v][i - 1][0].ff + S[u] - p[v]), v);
			for(auto j : {0, 1}){
				if(p1 >= dp1[u][i][j]) swap(p1, dp1[u][i][j]);
				if(p2 >= dp2[u][i][j]) swap(p2, dp2[u][i][j]);
			}
		}
	}
}
/*
void dfs2(int u, int par = 0){
	for(int v:adj[u]){
		if(v == par) continue;
		for(int i = 0; i <= k; ++i){
			pii p1 = dp1[v][i][0], p2 = dp1[v][i][1];
			pii p3 = dp2[u][k - i][0], p4 = dp2[u][k - i][1];
			int t = (p3.ss == v ? p4.ff + p1.ff : p3.ff + p1.ff);
			ans = max(t, ans);
		}
		dfs2(v, u);
	}
}
*/
void solve(){
	int n; cin >> n >> k;
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= k; ++j){
			dp1[i][j][0] = dp1[i][j][1] = mp(-1e18, -1);
			dp2[i][j][0] = dp2[i][j][1] = mp(-1e18, -1);
		}
	}
	for(int i = 1; i <= n; ++i) cin >> p[i];
	for(int j = 1; j <= n - 1; ++j){
		int u, v; cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	for(int i = 1; i <= n; ++i){
		for(auto v:adj[i]){
			S[i] += p[v];
		}
	}
	dfs(1);
	//dfs2(1);
	for(int i = 1; i <= n; ++i){
		for(int j = 0; j <= k; ++j){
			pii p1 = dp1[i][j][0], p2 = dp1[i][j][1];
			pii p3 = dp2[i][k - j][0], p4 = dp2[i][k - j][1];
			int t = (p3.ss == p1.ss ? max(p3.ff + p2.ff, p4.ff + p1.ff) : p3.ff + p1.ff);
			ans = max(t, ans);
		}
	}
	cout << ans << '\n';
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1; //cin >> t;
	while(t--) solve();
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 229 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -