제출 #948208

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
948208		amirhoseinfar1385	Chase (CEOI17_chase)	C++17	40 / 100	249 ms	97212 KiB

chase

#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10,maxv=102;
long long vis[maxn],n,mv,all[maxn],sz[maxn],mainres;
struct hal{
	vector<long long>adj[maxn];
	void con(long long u,long long v){
		adj[v].push_back(u);
	}
	long long res,tamam[maxv],fakeres[maxv],ezaf[maxv],dovom[maxv];
	void clear(){
		res=0;
		for(long long i=0;i<maxv;i++){
			tamam[i]=fakeres[i]=ezaf[i]=dovom[i]=0;
		}
		for(long long i=0;i<maxn;i++){
			adj[i].clear();
		}
	}
	void build(long long u,long long par=-1){
		long long suma=0;
		for(auto x:adj[u]){
			if(x==par){
				continue;
			}
			suma+=all[x];
		}
		for(long long i=1;i<=mv;i++){
			int wt=0;
			if(par!=-1){
				wt=all[par];
			}
			res=max(res,suma+fakeres[i-1]+tamam[mv-i]+wt);
			if(par!=-1&&i>0){
				ezaf[i]=max(ezaf[i],dovom[i-1]+suma);
			}
		}
		long long hey[maxv],hey2[maxv];
		for(int i=0;i<maxv;i++){
			hey[i]=fakeres[i];
			hey2[i]=dovom[i];
		}
		for(auto x:adj[u]){
			if(x==par){
				continue;
			}
			int wt=0;
			if(par!=-1){
				wt=all[par];
			}
			for(long long i=mv;i>=1;i--){
				fakeres[i]=max(fakeres[i],fakeres[i-1]+suma-all[x]+wt);
				if(par!=-1)
					dovom[i]=max(dovom[i],dovom[i-1]+suma);
			}
			build(x,u);
			for(int i=0;i<maxv;i++){
				fakeres[i]=hey[i];
				dovom[i]=hey2[i];
			}
			if(par==-1){
				for(long long i=0;i<=mv;i++){
					tamam[i]=max(tamam[i],ezaf[i]);
					ezaf[i]=0;
				}
			}
		}
	}
}ds;

vector<long long>adj[maxn];

void vorod(){
	cin>>n>>mv;
	for(long long i=1;i<=n;i++){
		cin>>all[i];
	}
	for(long long i=0;i<n-1;i++){
		long long u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
}

void calsz(long long u,long long par=-1){
	sz[u]=1;
	for(auto x:adj[u]){
		if(vis[x]||x==par){
			continue;
		}
		calsz(x,u);
		sz[u]+=sz[x];
	}
}

long long findcent(long long u,long long s,long long par=-1){
	for(auto x:adj[u]){
		if(x!=par&&vis[x]==0&&sz[x]*2>s){
			return findcent(x,s,u);
		}
	}
	return u;
}

void pass(long long u,long long par=-1){
	for(auto x:adj[u]){
		if(vis[x]==0&&x!=par){
			ds.con(x,u);
			pass(x,u);
		}
	}
}

void cal(long long u){
	ds.clear();
	pass(u);
	ds.build(u);
	mainres=max(mainres,ds.res);
	ds.clear();
	pass(u);
	reverse(ds.adj[u].begin(),ds.adj[u].end());
	ds.build(u);
	mainres=max(mainres,ds.res);
}

void solve(long long u=1){
	calsz(u);
	long long v=findcent(u,sz[u]);
	cal(v);
	vis[v]=1;
	for(auto x:adj[v]){
		if(vis[x]==0){
			solve(x);
		}
	}
}

void khor(){
	cout<<mainres<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//freopen("inp.txt","r",stdin);
	vorod();
	if(n<=1000){
		solve();
	}else{
		cal(1);
	}
	khor();
}

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