제출 #161888

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
161888		amoo_safar	Chase (CEOI17_chase)	C++14	50 / 100	555 ms	174712 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 = 103;
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();
	dp1[u][1] = sm;
	for(auto adj : G[u]){
		if(adj != pa) S.pb(adj);
	}
	for(auto adj : S){
		dp1[u][1] = sm;
		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);
	mx[1] = sm;
	for(auto adj : S){
		for(int i = 0; i <= V; i++) ans = max(ans, mx[V - i] + dp2[adj][i]);
		ans = max(ans, mx[V]);
		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]);
		for(int i = 1; i <= V; i++) mx[i] = max(mx[i], mx[i - 1]);
	}
	reverse(all(S));
	memset(mx, 0, sizeof mx);
	mx[1] = sm;
	for(auto adj : S){
		for(int i = 0; i <= V; i++) ans = max(ans, mx[V - i] + dp2[adj][i]);
		ans = max(ans, mx[V]);
		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]);
		for(int i = 1; i <= V; i++) mx[i] = max(mx[i], mx[i - 1]);
	}
}

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;
}
/*
12 2
2 3 3 8 1 5 6 7 8 3 5 4
2 1 
2 7
3 4
4 7 
7 6
5 6
6 8
6 9
7 10
10 11
10 12

*/

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