Submission #1052478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052478		TAhmed33	Chase (CEOI17_chase)	C++98	0 / 100	757 ms	178612 KiB

chase

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 25;
ll dp[MAXN][101], p[MAXN], ans[MAXN], s[MAXN];
ll dp2[MAXN][101];
vector <int> adj[MAXN];
int n, v; 
ll mx = 0;
void dfs (int pos, int par) {
	for (auto j : adj[pos]) {
		if (j != par) {
			dfs(j, pos);
		}
	}
	vector <pair <ll, ll>> ii[v + 1];
	vector <pair <ll, ll>> ii2[v + 1];
	ii[0].push_back({0, 0}); ii2[0].push_back({0, 0});
	ii[0].push_back({0, 0}); ii2[0].push_back({0, 0});
	for (int i = 1; i <= v; i++) {
		dp[pos][i] = 0; dp2[pos][i] = 0;
		for (auto j : adj[pos]) {
			if (j != par) {
				ll x = max(dp[j][i], dp[j][i - 1] + s[j] - p[pos]);
				dp[pos][i] = max(dp[pos][i], x);
				ii[i].push_back({x, j});
				x = max(dp2[j][i], dp2[j][i - 1] + s[pos] - p[j]);
				dp2[pos][i] = max(dp2[pos][i], x);
				ii2[i].push_back({x, j});
			}
		}
		dp2[pos][i] = max(dp2[pos][i], s[pos]);
		ii2[i].push_back({s[pos], 0});
	}
	for (int i = 1; i <= v; i++) {
		sort(ii[i].begin(), ii[i].end());
		sort(ii2[i].begin(), ii2[i].end());
	}
	for (int i = 0; i <= v; i++) {
		for (auto j : adj[pos]) {
			if (j == par) continue;
			if (j == ii[i].back().second) {
				mx = max(mx, ii[i][int(ii[i].size()) - 2].first + dp2[j][v - i]);
			} else {
				mx = max(mx, dp[pos][i] + dp2[j][v - i]);
			}
		}
	}
}
void solve () {
	cin >> n >> v;
	for (int i = 1; i <= n; i++) {
		cin >> p[i];
	}
	for (int i = 1; i < n; i++) {
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
		s[a] += p[b]; s[b] += p[a];
	}
	dfs(1, -1);
	cout << mx << '\n';
}		
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; //cin >> tc;
	while (tc--) solve();
}	

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