Submission #379729

#	Time	Username	Problem	Language	Result	Execution time	Memory
379729		errorgorn	Chase (CEOI17_chase)	C++17	100 / 100	579 ms	263788 KiB

chase

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front

#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);(s<e?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

int n,k;
ll arr[100005];
vector<int> al[100005];

ll adj[100005];
ll w1[100005][105]; //asc
ll w2[100005][105]; //dsc

ll ans=0;

void dfs(int i,int p){
	ll temp1[105];
	ll temp2[105];
	ll temp3[105];
	
	memset(temp1,0,sizeof(temp1));
	memset(temp2,0,sizeof(temp2));
	memset(temp3,0,sizeof(temp3));
	
	for (auto &it:al[i]){
		if (it==p) continue;
		
		dfs(it,i);
		
		rep(x,0,k){ //combine 2 and this is taken
			ans=max(ans,temp1[k-x-1]+w2[it][x]+adj[i]-arr[it]);
			ans=max(ans,w1[it][x]+temp2[k-x-1]+adj[i]);
		}
		rep(x,0,k){
			ans=max(ans,temp1[k-x]+w2[it][x]);
			ans=max(ans,w1[it][x]+temp3[k-x]);
		}
		
		rep(x,0,k){
			ans=max(ans,w1[it][x]+adj[i]);
			w1[i][x]=max(w1[i][x],w1[it][x]);
			if (p!=-1) w1[i][x+1]=max(w1[i][x+1],w1[it][x]+adj[i]-arr[p]);
			
			temp1[x]=max(temp1[x],w1[it][x]);
		}
		rep(x,0,k){
			ans=max(ans,w2[it][x]+adj[i]-arr[it]);
			w2[i][x]=max(w2[i][x],w2[it][x]);
			w2[i][x+1]=max(w2[i][x+1],w2[it][x]+adj[i]-arr[it]);
			
			temp2[x]=max(temp2[x],w2[it][x]-arr[it]);
			temp3[x]=max(temp3[x],w2[it][x]);
		}
	}
	
	rep(x,1,k) w2[i][x]=max(w2[i][x],adj[i]);
	
	//cout<<"ans: "<<i<<" "<<ans<<endl;
	
	//cout<<i<<": "<<endl;
	//rep(x,0,k) cout<<w1[i][x]<<" "; cout<<endl;
	//rep(x,0,k) cout<<w2[i][x]<<" "; cout<<endl;
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>k;
	rep(x,1,n+1) cin>>arr[x];
	
	int a,b;
	rep(x,1,n){
		cin>>a>>b;
		al[a].pub(b);
		al[b].pub(a);
		
		adj[a]+=arr[b];
		adj[b]+=arr[a];
	}
	
	/*
	dfs(4,-1);
	cout<<ans<<endl;
	return 0;
	*/
	
	dfs(1,-1);
	
	cout<<ans<<endl;
}

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