Submission #921622

#	Time	Username	Problem	Language	Result	Execution time	Memory
921622		PM1	Chase (CEOI17_chase)	C++17	0 / 100	4041 ms	73160 KiB

chase

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mxn=1e5+5,mxv=102;
ll n,vv,p[mxn],par[mxn],sz[mxn];
ll a[mxn],dp[3][mxn][mxv],ans,mx[3][mxv];
vector<ll>v[mxn];
void fds(ll z,ll root ,ll poot){
	for(ll i=1;i<=vv;i++){
		dp[0][z][i]=max({dp[0][z][i-1],dp[0][par[z]][i-1]+a[z]-p[par[z]],dp[0][par[z]][i]});
		ans=max(ans,dp[0][z][i]+mx[1][vv-i]-p[root]);
		ans=max(ans,dp[0][z][i]+mx[2][vv-i]);
	}
	for(auto j:v[z]){
		if(par[z]!=j){
			fds(j,root,poot);
			for(ll i=1;i<=vv;i++){
				dp[1][z][i]=max({dp[1][z][i-1],dp[1][j][i-1]+a[z]-p[j],dp[2][j][i-1]+a[z]-p[j]});
				dp[2][z][i]=max({dp[2][z][i-1],dp[2][j][i],dp[1][j][i]});
			}
		}
	}
	for(ll i=1;i<=vv;i++){
		dp[1][z][i]=max(dp[1][z][i-1],a[z]);
	}
	if(z==poot){
		for(ll i=1;i<=vv;i++){
			ans=max(ans,dp[1][z][i]+mx[0][vv-i]-p[poot]);
			ans=max(ans,dp[2][z][i]+mx[0][vv-i]);
		}
	}
}
void up(ll z){
	for(ll i=1;i<=vv;i++){
		dp[0][z][i]=max({dp[0][z][i-1],dp[0][par[z]][i-1]+a[z]-p[par[z]],dp[0][par[z]][i]});
		mx[0][i]=max(mx[0][i],dp[0][z][i]);
	}
	for(auto j:v[z]){
		if(par[z]!=j){
			up(j);
			for(ll i=1;i<=vv;i++){
				dp[1][z][i]=max({dp[1][z][i-1],dp[1][j][i-1]+a[z]-p[j],dp[2][j][i-1]+a[z]-p[j]});
				dp[2][z][i]=max({dp[2][z][i-1],dp[2][j][i],dp[1][j][i]});
				mx[1][i]=max(mx[1][i],dp[1][z][i]);
				mx[2][i]=max(mx[2][i],dp[2][z][i]);
			}
		}
	}
	for(ll i=1;i<=vv;i++){
		dp[1][z][i]=max(dp[1][z][i-1],a[z]);
		mx[1][i]=max(mx[1][i],dp[1][z][i]);
		mx[2][i]=max(mx[2][i],dp[2][z][i]);
	}
}
void dfs(ll z){
	sz[z]=1;
	ll big=0;
	for(auto i:v[z]){
		if(par[z]!=i){
			par[i]=z;
			dfs(i);
			sz[z]+=sz[i];
			if(sz[big]<sz[i])big=i;
		}
	}
	for(ll i=1;i<=vv;i++)
		dp[0][z][i]=a[i];
	if(big!=0){
		up(big);		
		for(ll i=1;i<=vv;i++){
			dp[1][z][i]=max({dp[1][z][i-1],dp[1][big][i-1]+a[z]-p[big],dp[2][big][i-1]+a[z]-p[big]});
			dp[2][z][i]=max({dp[2][z][i-1],dp[2][big][i],dp[1][big][i]});
			ans=max({ans,dp[1][z][i],dp[2][z][i]});
		}
	}	
	for(auto j:v[z]){
		if(par[z]!=j && j!=big){
			fds(j,z,j);
			up(j);
			for(ll i=1;i<=vv;i++){
				dp[1][z][i]=max({dp[1][z][i-1],dp[1][j][i-1]+a[z]-p[j],dp[2][j][i-1]+a[z]-p[j]});
				dp[2][z][i]=max({dp[2][z][i-1],dp[2][j][i],dp[1][j][i]});
				ans=max({ans,dp[1][z][i],dp[2][z][i]});
			}
		}
	}
	for(int i=1;i<=vv;i++){
		for(int j=0;j<3;j++)
			ans=max(ans,mx[j][i]);
	}
	//cout<<z<<" "<<ans<<endl;
	memset(mx,0,sizeof mx);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>vv;
	for(ll i=1;i<=n;i++)
		cin>>p[i];
	for(ll i=1;i<n;i++){
		ll x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
		a[x]+=p[y];
		a[y]+=p[x];
	}
	//cout<<endl;
	dfs(1);
	cout<<ans<<endl;
}

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