제출 #1247577

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247577		MateiKing80	Chase (CEOI17_chase)	C++20	100 / 100	596 ms	173180 KiB

chase

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll

#define jos 0
#define sus 1

const int N = 1e5 + 5, V = 105, inf = 1e16;

int dp[2][V][N], p[N], v, ans;
vector<int> vec[N];

void dfs(int nod, int papa) {
	for (auto i : vec[nod])
		if (i != papa)
			dfs(i, nod);
	int sumvec = 0;
	for (auto i : vec[nod])
		if (i != papa)
			sumvec += p[i];
	dp[jos][1][nod] = sumvec + p[papa];
	for (auto i : vec[nod]) {
		if (i == papa)
			continue;
		for (int j = 0; j <= v; j ++) {
			dp[sus][j][nod] = max(dp[sus][j][nod], dp[sus][j][i]);
			if (j)
				dp[sus][j][nod] = max(dp[sus][j][nod], dp[sus][j - 1][i] + sumvec);
		}
	}
	for (auto i : vec[nod]) {
		if (i == papa)
			continue;
		for (int j = 0; j <= v; j ++) {
			dp[jos][j][nod] = max(dp[jos][j][nod], dp[jos][j][i]);
			if (j)
				dp[jos][j][nod] = max(dp[jos][j][nod], dp[jos][j - 1][i] + sumvec - p[i] + p[papa]);
		}
	}
	//nu punem in nod -> max(dp[jos][i][x] + dp[sus][v - i][y]; x != y DIFERITE (sa nu vina din acelasi loc
	vector<vector<int>> vsus(2, vector<int> (v + 1));
	for (auto i : vec[nod]) {
		if (i == papa)
			continue;
		for (int j = 0; j <= v; j ++) {
			if (dp[sus][j][i] > vsus[0][j]) {
				vsus[1][j] = vsus[0][j];
				vsus[0][j] = dp[sus][j][i];
			} else if (dp[sus][j][i] > vsus[1][j]) {
				vsus[1][j] = dp[sus][j][i];
			}
		}
	}
	for (auto i : vec[nod]) {
		if (i == papa)
			continue;
		for (int j = 0; j <= v; j ++)
			ans = max(ans, dp[jos][j][i] + (dp[sus][v - j][i] == vsus[0][v - j] ? vsus[1][v - j] : vsus[0][v - j]));
		for (int j = 0; j < v; j ++)
			ans = max(ans, dp[jos][j][i] + sumvec + p[papa] - p[i] + (dp[sus][v - j - 1][i] == vsus[0][v - j - 1] ? vsus[1][v - j - 1] : vsus[0][v - j - 1]));
	}
	//punem in nod -> max(dp[jos][i][x] + dp[sus][v - i - 1][y] + sumvec[nod] + p[papa] - p[x])
	
	
	//incepem si terminam in nod
	if (v)
		ans = max(ans, sumvec);
	
	//incepem in nod
	ans = max(ans, vsus[0][v]);
	for (auto i : vec[nod])
		if (i != papa && v)
			ans = max(ans, dp[sus][v - 1][i] + sumvec + p[papa]);
	
	//terminam in nod
	for (auto i : vec[nod])
		if (i != papa) {
			if (v)
				ans = max(ans, dp[jos][v - 1][i] + sumvec + p[papa] - p[i]);
			ans = max(ans, dp[jos][v][i]);
		}
	
	
	for (int i = 1; i <= v; i ++) {
		dp[jos][i][nod] = max(dp[jos][i][nod], dp[jos][i - 1][nod]);
		dp[sus][i][nod] = max(dp[sus][i][nod], dp[sus][i - 1][nod]);
	}
	
	
	
	/*
	acum partea in care chiar calculez raspunsul
	trebuie unite astea
	adica trebe sa vina sus de undeva si jos de altundeva
	SAU incepe / se termina in nod
	*/
}
/*
dp[jos] va fi calculat cu toti vecinii si dupa va trebui 
sa scoatem ala in care ne ducem
*/
signed main() {
	bool afis = false;
	int n;
	cin >> n >> v;
	for (int i = 1; i <= n; i ++)
		cin >> p[i];
	dp[sus][0][0] = dp[jos][0][0] = -inf;
	for (int i = 1; i < n; i ++) {
		int x, y;
		cin >> x >> y;
		vec[x].push_back(y);
		vec[y].push_back(x);
	}
	dfs(1, 0);
	if (afis) {
		cout << "SUS\n";
		for (int i = 1; i <= n; i ++, cout << '\n') {
			cout << "Nod: " << i << "     ";
			for (int j = 0; j <= v; j ++)
				cout << dp[sus][j][i] << " ";
		}
		cout << "JOS\n";
		for (int i = 1; i <= n; i ++, cout << '\n') {
			cout << "Nod: " << i << "     ";
			for (int j = 0; j <= v; j ++)
				cout << dp[jos][j][i] << " ";
		}
	}
	cout << ans << '\n';
}
/*
poti zice dp[sus/jos][paine][nod];
practic eu adun toti vecinii prin care nu am trecut inainte
este clar ca vreau sa arunc paine la primu nod prin care trec
*/

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