Submission #939576

#	Time	Username	Problem	Language	Result	Execution time	Memory
939576		Baytoro	Chase (CEOI17_chase)	C++17	100 / 100	247 ms	180052 KiB

chase

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fr first
#define sc second
#define ll long long
#define int long long
const int N=1e5+5;
int p[N];
vector<int> g[N];
int c[N][105],b[N][105];
int G(int x){
	//int res=-=p[par];
	int res=0;//<---------------
	for(auto it: g[x]){
		res+=p[it];
	}
	return res;
}
int n,k;
int ans=0;
void dfs(int x, int par){
	int sum=G(x);
	b[x][1]=sum;
	for(auto it: g[x]){
		if(it==par) continue;
		dfs(it,x);
		
		for(int j=1;j<=k;j++){
			ans=max(ans,b[x][j]+c[it][k-j]);
			c[x][j]=max(c[x][j],max(c[it][j],c[it][j-1]+sum-p[par]));
			b[x][j]=max(b[x][j],max(b[it][j],b[it][j-1]+sum-p[it]));
		}
			
	}
	reverse(all(g[x]));
	memset(c[x],0,sizeof c[x]);
	memset(b[x],0,sizeof b[x]);
	b[x][1]=sum;
	for(auto it: g[x]){
		if(it==par) continue;
		
		for(int j=1;j<=k;j++){
			ans=max(ans,b[x][j]+c[it][k-j]);
			c[x][j]=max(c[x][j],max(c[it][j],c[it][j-1]+sum-p[par]));
			b[x][j]=max(b[x][j],max(b[it][j],b[it][j-1]+sum-p[it]));
		}
			
	}
}
void solve(){
	//int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>p[i];
	for(int i=1;i<n;i++){
		int a,b;cin>>a>>b;
		g[a].pb(b);
		g[b].pb(a);
	}
	dfs(1,0);
	cout<<ans<<endl;
}
main(){
    int T=1;
    //cin>>T;
    while(T--){
        solve();
    }
}
/*
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
*/

Compilation message (stderr)

chase.cpp:66:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   66 | main(){
      | ^~~~

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