Submission #60210

#	Time	Username	Problem	Language	Result	Execution time	Memory
60210		thiago4532	Chase (CEOI17_chase)	C++14	40 / 100	4101 ms	357128 KiB

chase

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 10, maxk = 1e2 + 10;
vector<int> grafo[maxn];
int n, k;
ll gain[maxn], x[maxn], dp[2][maxn][maxk], dp2[2][maxn][maxk], ans[maxn];

void dfs(int u, int p=0){
	gain[u] = 0;
	for(auto v : grafo[u]){
		if(v == p) continue;
		gain[u] += x[v];

		dfs(v, u);
	}
}

inline void calcDp(int u, int p=0){
	for(int l=1;l<=k;l++)
		for(int x=0;x<2;x++) dp[x][u][l] = dp2[x][u][l] = 0;
	
	for(auto v : grafo[u]){
		if(v == p) continue;

		for(int l=1;l<=k;l++){
			ll x = max(dp[0][v][l], dp[1][v][l]);
			ll y = max(dp[0][v][l-1], dp[1][v][l-1]) + gain[u];

			if(dp[0][u][l] < y) dp2[0][u][l] = dp[0][u][l], dp[0][u][l] = y;
			else if(dp2[0][u][l] < y) dp2[0][u][l] = y;

			if(dp[1][u][l] < x) dp2[1][u][l] = dp[1][u][l], dp[1][u][l] = x;
			else if(dp2[1][u][l] < x) dp2[1][u][l] = x;
		}
	}
}

void solve(int u, int p=0){
	for(int l=1;l<=k;l++)
		for(int x=0;x<2;x++) dp[x][u][l] = dp2[x][u][l] = 0;
	
	for(auto v : grafo[u]){
		if(v == p) continue;
		solve(v, u);
	
		for(int l=1;l<=k;l++){
			ll x = max(dp[0][v][l], dp[1][v][l]);
			ll y = max(dp[0][v][l-1], dp[1][v][l-1]) + gain[u];

			if(dp[0][u][l] < y) dp2[0][u][l] = dp[0][u][l], dp[0][u][l] = y;
			else if(dp2[0][u][l] < y) dp2[0][u][l] = y;

			if(dp[1][u][l] < x) dp2[1][u][l] = dp[1][u][l], dp[1][u][l] = x;
			else if(dp2[1][u][l] < x) dp2[1][u][l] = x;
		}
	}
}

void rotate(int u, int p=0){
	ans[u] = max(dp[0][u][k], dp[1][u][k]);
	// cout << "ans(" << u << "): " << ans[u] << " " << max(dp2[0][u][k], dp2[1][u][k]) << "\n";
	ll x3[maxk], x4[maxk], x5[maxk], x6[maxk], x7[maxk], x8[maxk];

	for(auto v : grafo[u]){
		if(v == p) continue;

		ll x1 = gain[u], x2 = gain[v];

		for(int l=1;l<=k;l++)
			x3[l] = dp[0][u][l], x4[l] = dp[1][u][l], x5[l] = dp[0][v][l], x6[l] = dp[1][v][l], x7[l] = dp2[0][v][l], x8[l] = dp2[1][v][l];

		for(int l=1;l<=k;l++){
			ll a = max(dp[0][v][l], dp[1][v][l]);
			ll b = max(dp[0][v][l-1], dp[1][v][l-1]) + gain[u];

			if(dp[1][u][l] == a) dp[1][u][l] = dp2[1][u][l];
			if(dp[0][u][l] == b) dp[0][u][l] = dp2[0][u][l];

			if(dp[0][u][l] != 0) dp[0][u][l] -= x[v];
		}


		gain[u] -= x[v];
		gain[v] += x[u];

		calcDp(v);
		rotate(v, u);

		gain[u] = x1, gain[v] = x2;
		for(int l=1;l<=k;l++)
			dp[0][u][l] = x3[l], dp[1][u][l] = x4[l], dp[0][v][l] = x5[l], dp[1][v][l] = x6[l], dp2[0][v][l] = x7[l], dp2[1][v][l] = x8[l];

	}
}

int main(){
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> k;
	for(int i=1;i<=n;i++)
		cin >> x[i];

	for(int i=1;i<n;i++){
		int a, b;
		cin >> a >> b;

		grafo[a].push_back(b);
		grafo[b].push_back(a);
	}

	dfs(1);
	solve(1);
	// rotate(1);

	// ll resp=0;
	// for(int i=1;i<=n;i++){
	// 	// cout << "gain: " << gain[i] << "\n";
	// 	// cout << "dp: " << dp[i][k] << "\n";
	// 	resp = max(resp, ans[i]);
	// }

	ll resp2=0;
	for(int i=1;i<=n;i++){
		dfs(i);
		solve(i);

		resp2 = max({resp2, dp[0][i][k], dp[1][i][k]});
		// cout << "ans2(" << i << "): " << max(dp[0][i][k], dp[1][i][k]) << " " << max(dp2[0][i][k], dp2[1][i][k]) << "\n";
	}

	// cout << resp << "\n";
	cout << resp2 << "\n";
	return 0;
}

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