Submission #161895

#	Time	Username	Problem	Language	Result	Execution time	Memory
161895		amoo_safar	Chase (CEOI17_chase)	C++14	100 / 100	582 ms	170896 KiB

chase

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
const ll Mod = 998244353;
const ll Inf = 2242545357980376863LL;
const ll Log = 20;
const ll N = 1ll << Log;
const int Maxn = 1e5 + 10;
const int Maxk = 101;
const int Base = 101;
 
ll dp1[Maxn][Maxk], dp2[Maxn][Maxk], p[Maxn];
vector<ll> G[Maxn];
 
vector<ll> S;
ll V, ans = 0;
 
ll mx[Maxk];
 
void DFS(ll u, ll pa){
	//debug(u);
	ll sm = 0;
	for(auto adj : G[u]){
		sm += p[adj];
		if(adj != pa) DFS(adj, u);
	}
	//cerr << u << " " << sm << '\n';
	ll sm2 = sm - (pa != -1 ? p[pa] : 0);
	S.clear();
	for(auto adj : G[u]){
		if(adj != pa) S.pb(adj);
		dp1[u][1] = max(sm, dp1[u][1]);
		for(int i = 1; i <= V; i++){
			dp1[u][i] = max({dp1[u][i], dp1[adj][i], dp1[adj][i - 1] + sm - p[adj] });
			dp2[u][i] = max({dp2[u][i], dp2[adj][i], dp2[adj][i - 1] + sm2 });
			ans = max({ans, dp1[u][i], dp2[u][i], dp2[adj][i - 1] + sm});
		}
	}
	
	if(S.size() < 2) return ;
	for(auto adj : S){
		for(int i = 1; i <= V; i++) dp1[adj][i] = max(dp1[adj][i], dp1[adj][i - 1]);
		for(int i = 1; i <= V; i++) dp2[adj][i] = max(dp2[adj][i], dp2[adj][i - 1]);
	}
	
	memset(mx, 0, sizeof mx);
	for(auto adj : S){
		for(int i = 0; i <= V; i++) ans = max(ans, mx[V - i] + dp2[adj][i]);
		
		for(int i = 0; i <= V; i++) mx[i] = max(mx[i], dp1[adj][i]);
		for(int i = 1; i <= V; i++) mx[i] = max(mx[i], dp1[adj][i - 1] + sm - p[adj]);
	}
	reverse(all(S));
	memset(mx, 0, sizeof mx);
	for(auto adj : S){
		for(int i = 0; i <= V; i++) ans = max(ans, mx[V - i] + dp2[adj][i]);
		
		for(int i = 0; i <= V; i++) mx[i] = max(mx[i], dp1[adj][i]);
		for(int i = 1; i <= V; i++) mx[i] = max(mx[i], dp1[adj][i - 1] + sm - p[adj]);
	}
}
 
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n;
	cin >> n >> V;
	for(int i = 1; i <= n; i++) cin >> p[i];
	ll u, v;
	for(int i = 1; i < n; i++){
		cin >> u >> v;
		G[u].pb(v);
		G[v].pb(u);
	}
	DFS(1, -1);
	cout << ans << '\n';
	return 0;
}

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