Submission #394791

#	Time	Username	Problem	Language	Result	Execution time	Memory
394791		Nima_Naderi	Chase (CEOI17_chase)	C++14	100 / 100	806 ms	169052 KiB

chase

//In the name of God
//#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 1e5 + 5;
const ll MXM = 100 + 5;
ll n, k, ans;
ll dp[MXM][MXN], pd[MXM][MXN], fp[MXM];
ll P[MXN], N[MXN], F[MXN];
vector<ll> adj[MXN];
void DFS(ll u, ll par){
	pd[1][u] = N[u];
	F[u] = N[u] - P[par];
	for(auto v : adj[u]) if(v != par) DFS(v, u);
	for(auto v : adj[u]){
		if(v != par){
			memset(fp, 0, sizeof fp);
			for(int j = 0; j <= k; j ++){
				fp[j] = max(fp[j], pd[j][v]);
				if(j) fp[j] = max(fp[j], pd[j - 1][v] + N[u] - P[v]);
			}
			for(int j = 0; j <= k; j ++) ans = max(ans, fp[j] + dp[k - j][u]);
			for(int j = 0; j <= k; j ++) pd[j][u] = max(pd[j][u], fp[j]);
			for(int j = 0; j <= k; j ++) dp[j][u] = max(dp[j][u], dp[j][v]);
		}
	}
	if(adj[u].size() > 1){
		reverse(adj[u].begin(), adj[u].end());
		for(int j = 0; j <= k; j ++) dp[j][u] = 0;
		for(auto v : adj[u]){
			if(v != par){
				memset(fp, 0, sizeof fp);
				for(int j = 0; j <= k; j ++){
					fp[j] = max(fp[j], pd[j][v]);
					if(j) fp[j] = max(fp[j], pd[j - 1][v] + N[u] - P[v]);
				}
				for(int j = 0; j <= k; j ++) ans = max(ans, fp[j] + dp[k - j][u]);
				for(int j = 0; j <= k; j ++) dp[j][u] = max(dp[j][u], dp[j][v]);
			}
		}
	}
	for(int j = 0; j < k; j ++){
		ans = max(ans, N[u] + dp[j][u]);
	}
	for(auto v : adj[u]){
		if(v != par){
			for(int j = 1; j <= k; j ++){
				dp[j][u] = max(dp[j][u], dp[j - 1][v] + F[u]);
			}
		}
	}
	dp[1][u] = max(dp[1][u], F[u]);
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
	cin >> n >> k;
	for(int i = 1; i <= n; i ++) cin >> P[i];
	for(int i = 1; i < n; i ++){
		ll u, v; cin >> u >> v;
		adj[u].push_back(v), adj[v].push_back(u);
		N[u] += P[v], N[v] += P[u];
	}
	DFS(1, 0);
	for(int i = 1; i <= n; i ++) ans = max(ans, dp[k][i]);
	for(int i = 1; i <= n; i ++) ans = max(ans, pd[k][i]);
	cout << ans << '\n';
	return 0;
}
//! N.N

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