Submission #54909

#	Time	Username	Problem	Language	Result	Execution time	Memory
54909		istlemin	Chase (CEOI17_chase)	C++14	50 / 100	2953 ms	104652 KiB

chase

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

ll n, bread;
vi p;
vector<vi> e;

vector<vi> mem;

ll dfs(ll v, ll l, ll b){
	if(b==0) return 0;
    if(mem[v][b]!=-1) return mem[v][b];
    ll best = 0;
    ll childSum = 0;
    rep(i,0,e[v].size())
		if(e[v][i]!=l)
			childSum += p[e[v][i]];

    rep(i,0,e[v].size()){
		if(e[v][i]==l) continue;
        best = max(best,childSum + dfs(e[v][i],v,b-1));
        best = max(best,dfs(e[v][i],v,b));
    }

    return mem[v][b] = best;
}

ll getBest(ll start){
    mem.assign(n,vi(bread+1,-1));
    return dfs(start,-1, bread);
}

int main(){
	cin.sync_with_stdio(false);
    cin>>n>>bread;
    p.resize(n);
    e.resize(n);
    rep(i,0,n) cin>>p[i];
	rep(i,0,n-1) {
		ll a,b;
		cin>>a>>b;
		--a; --b;
        e[a].push_back(b);
        e[b].push_back(a);
	}
    if(n>100){
		cout<<getBest(0)<<endl;
    } else {
		//cout<<getBest(5)<<endl;
		//return 0;
        ll best = 0;
        rep(i,0,n)
			best = max(best,getBest(i));
		cout<<best<<endl;
    }
}

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